ハノイの塔の問題は、3本の棒と、最初に1本の棒に積まれた異なる大きさの円盤が与えられ、全ての円盤を最初の棒から最後の棒に移す問題です。ただし、これを行う際には以下のルールがあります。
- 1度に1つの円盤しか移動できない。
- より大きい円盤がより小さい円盤の上に置かれることはできない。
この問題は、フランスの数学者エドゥアール・リュカによって考案され、当初は「ラ・トール・ド・ハノイ」と呼ばれていました。
解法には再帰関数が用いられます。以下に、3つの円盤を持つ場合の手順を示します。
- 最初の棒にある全ての円盤を、中央の棒を介して最後の棒に移す。
- 最初の棒にある最大の円盤を最後の棒に移す。
- 中央の棒にある全ての円盤を、最初の棒を介して最後の棒に移す。
この手順を再帰的に繰り返すことで、全ての円盤を最初の棒から最後の棒に移すことができます。
具体的な手順を表すと、
- 3つの円盤を移す場合の手順
function hanoi(n, from, via, to) { if (n === 1) { console.log(from + " -> " + to); } else { hanoi(n - 1, from, to, via); console.log(from + " -> " + to); hanoi(n - 1, via, from, to); } } hanoi(3, "A", "B", "C"); // 出力: A -> C, A -> B, C -> B, A -> C, B -> A, B -> C, A -> C
このように、再帰的な手法によって、任意の数の円盤を移動することができます。ハノイの塔の問題は、そのシンプルなルールと再帰的な解法から、プログラミングのアルゴリズムなどに応用されることがあります。