ネタ元 → 開発記その13
あーなつかしぃハノイの塔。
再帰呼び出しの例として階乗(factorial)に次ぐ人気(?)
大きさ1,2,...NのN枚の円盤がある。
どれも真ん中に穴が空いていて、三本の棒A,B,Cのひとつに
最も大きいNを一番下にしてN,N-1,...2,1とまとめて挿さっている。
このN枚の円盤でできたハノイの塔を他の棒に移し替えるワケ
だけど、 動かせるのは棒の一番上にある一枚だけ。
たとえばN=2だと
円盤 1 を Ａ から Ｂ へ
円盤 2 を Ａ から Ｃ へ
円盤 1 を Ｂ から Ｃ へ
ってな手順となります。
任意のNについて手順を示せ。てのが問題。
using System;
namespace Wankuma {
public class Hanoi {
// 円盤Nをfromからviaを使ってtoに移すには、
public static void Move(int N, char from, char via, char to) {
if ( N != 0 ) {
// Nの上に乗ったN-1枚をformからtoを使ってviaに退避させ、
Move(N-1, from, to, via);
// fromに残る円盤Nをtoに移して、
Console.WriteLine("円盤 {0} を {1} から {2} へ", N, from, to);
// viaにある退避させたN-1枚をfromを使ってtoに移す。
Move(N-1, via, from, to);
}
}
public static void Main() {
Move(5, 'Ａ', 'Ｂ', 'Ｃ');
}
}
}
N枚の円盤を移す手順の総数は2^N-1となります。
本家(?)ハノイの塔はN=64で、全部移し終わった途端
この世は消滅するそうです。
ですから上記コードでN=64での問題を実行する際は
実行したままうっかり寝ちゃわないように。
朝日を拝めなくなるかもしれません。