ハノイの搭を4本にしたら




ハノイの搭は再帰的プログラムの例として有名であり、 n枚の円盤を他の搭に移すのに2^n-1回の移動が必要です。
本来のハノイの搭は3本ですが、 4本以上にしたらどうなるかと考えてコンピューター で調べてみたら下の表のように非常に面白い数列が得られました。

円盤の枚数	1	2	3	4	5	6	7	8	9	10	11
3本のときの移動回数	1	3	7	15	31	63	127	255	511	1023	2047
4本のときの移動回数	1	3	5	9	13	17	25	33	41	49	65
5本のときの移動回数	1	3	5	7	11	15	19	23	27	31	39
6本のときの移動回数	1	3	5	7	9	13	17	21	25	29	33

JAVA plug-in がブラウザにinstallされているならば、
下の入力boxに1以上10以下の整数を入力してボタンをクリックしてみて下さい。

4 5 6 7 8 9 10 枚の円盤を　 の最小回数での移動の仕方を表示します。