ハノイの塔
ハノイの塔は、下図の様に、三本の柱と幾つかの大きさの異なるディスクからなっています。ディスクは、一枚づつ上からとって、別の柱に移動できますが、小さいディスクの上に大きいディスクを置くことはできない制限があります。
ハノイの塔を解くとは、最初の状態から、制限を守って、別の柱に全てのディスクを移動することです。
n 枚のディスクを、A から C へ移動するには、以下の操作を行えばできます。
- n 番目のディスクより上にあるディスクを、A から B へ移動する。
- n 番目のディスクを、A から C へ移動する。
- n 番目のディスクより上にあったディスクを、B から C へ移動する。
n 番目のディスクより上にあるディスクの移動は、n-1 枚のディスクの移動と同じになり、ここで再帰呼出しを行います。
再帰呼出しを使って、ハノイの塔を解くプログラムは以下のようになります。
var n = window.prompt("How many disks(1-4)?");
console.log("The number of disk : " + n);
hanoi(n, 'A', 'B', 'C');
function hanoi(n, a, b, c) {
if(n > 1) hanoi(n - 1, a, c, b);
console.log("Move disk No. " + n + " from " + a + " to " + c + ".");
if(n > 1) hanoi(n - 1, b, a, c);
}