ハノイの塔

3本の柱（[元柱], [予備柱], [目的柱]）があって、大きさの違う $n$ 枚の円板が右図のように順に[元柱]に積んである。 1枚ずつ柱から円板をはずし、別の柱に移す操作をしながら、[目的柱]に $n$ 枚の円板を移動したい。積み上がっている $n$ 枚の円板に上から（小さい方から）、円板[1], 円板[2],$\dots$, 円板[n] と番号を振っておく（$n\geqq 1$）。
[ルール]：小さな円板の上に大きな円板を置くことはできない。

左図は $n = 3$ 枚の円板が元柱にあるとき、ルールを破らないように、手順 (1), (2), (3), (4), (5), (6) によって、ゴールである (7) に至る7回の円板移動の様子を示している。これ以上少ない手順で円板を元柱から目的柱に移動させることはできない（本当？）

ハノイの塔の手順を表示するJavascript

ダイアログ『ハノイの塔の円板の枚数（1以上）を半角入力してください。』に、キーボードから半角で1以上の整数値 $n$ を入力して、円板[1],$\dots$, 円板[n] として、ハノイの塔のゲーム手順を表示するJavascriptを実行するリンクが次にある。

入力する半角整数は 1 から高々 5 程度としよう。円板を動かす回数は $2^n-1$ であることが分かってる（何故？）ため、大きな $n$ ではたいへんなことになるからである（$n=10$ で 1023行の移動記述が表示される）。

Webブラウザの文字符号化は UTF-8 でないと文字化けします (x_x)

ハノイの塔の手順を表示する
　　　　（ブラウザの[再読込みボタン]

を押せば、何度でも繰り返す）

ハノイの塔のアルゴリズムとその回数

左図のように柱 F に積み上がっている $n$ 枚の円板を柱 T に移動させる手順アルゴリズムを次のように書こう。

\[ \mathrm{Hanoi}(n, F, S, T) \]

理解の鍵は、左図のような移動（上の図(0)→(3)に相当）する手順である。つまり、柱 F にある上から $n-1$ 枚の円板を、柱 T を使いながら、柱 S に移動させる手順 $\mathrm{Hanoi}(n-1, F, T, S)$ が分かればよい。

そうすれば、柱 F に1枚残っている円板 [n] を柱 T に移した後に、今度は柱 S にある$n-1$枚の円板を柱 F を使いながら、柱 T に移動させる手順 $\mathrm{Hanoi}(n-1, S, F, T)$ を実行すると、目的の手順 $\mathrm{Hanoi}(n, F, S, T)$ を達成したことになる。つまり、求めるアルゴリズム $\mathrm{Hanoi}(n, F, S, T)$ は次のように表すことができる。

\begin{align*} \mathrm{Hanoi}(n, F, S, T)&=\\ & \begin{array}{l} \mathrm{Hanoi}(n-1, F, T, S)\\ \text{円板 [n] を柱 F から柱 T に移動}\\ \mathrm{Hanoi}(n-1, S, F, T) \end{array} \end{align*}

柱 F にある $n$ 枚の円板を柱 T に移動するために必要な円板の移動回数 $H_n$ を求めてみよう。上の手順 $\mathrm{Hanoi}(n, F, S, T)$ の関係式から、$H_n$ は次の関係（漸化式）を満足していることがわかる。 \begin{align} H_1 &= 1\\ H_n &= 2H_{n-1}+1 \end{align}

式(1)は、$n=1$ の時には、柱 F にある1枚の円板[1] を柱 T に1回移動すればよいからである。式(2)は、柱 F にある1枚の円板を柱 T に移動する回数 $H_n$ は、まず柱 F にある $n-1$ 枚の円板を柱 S に移動し（回数 $H_n$）、柱 F にある円板[n] を1回で柱 T に移動し、さらに柱 S にある $n-1$ 枚の円板を柱 T に移動する（回数 $H_n$）からである。

$H_n=2^n-1$（$n\geqq 1$）がこの漸化式の解であることは、直接代入して確かめられる。 $n$ 枚のハノイの塔のゲームには $=2^n-1$ 回の円板の移動が必要であることが分かった。