いわゆる、ハノイの塔をコンピューター上で再帰処理を行うことなく解くことを考える。
また、ｎ個のハノイの塔をとくには、２＾ｎ−１のステップが必要であることはよくしられている。
(よって、ここでその証明は省く。)

概要（実際に紙と鉛筆でやってみることをお勧めします）：

１個のハノイの塔をとく。

step-0	step-1
[1] _I_ _I_	_I_ _I_ [1]

動かしたこまの番号は順に、
１

２個のハノイの塔をとく。

step-0	step-1	step-2	step-3
[1] _I_ _I_ [2] _I_ _I_	_L_ _L_ _I_ [2] [1] _I_	_I_ _L_ _I_ _I_ [1] [2]	_I_ _I_ [1] _I_ _I_ [2]

動かしたこまの番号は順に、
１−２−１

３個のハノイの塔をとく。

step-0	step-1	step-2	step-3	step-4	step-5	step-6	step-7
[1] _I_ _I_ [2] _I_ _I_ [3] _I_ _I_	_L_ _I_ _I_ [2] _I_ _I_ [3] _I_ [1]	_L_ _L_ _I_ _L_ _L_ _I_ [3] [2] [1]	_L_ _L_ _I_ _L_ [1] _I_ [3] [2] _I_	_I_ _L_ _I_ _I_ [1] _I_ _I_ [2] [3]	_L_ _L_ _I_ _L_ _L_ _I_ [1] [2] [3]	_L_ _I_ _L_ _L_ _I_ [2] [1] _I_ [3]	_I_ _I_ [1] _I_ _I_ [2] _I_ _I_ [3]

ここで動かしたこまの番号は順に、
１−２−１−３−１−２−１
動かすこまの番号の順に、またその動きに規則性めいたものを感じることだろう。
ここから、その規則性を利用し問題を解くことに役立てることにする。

3個のハノイの塔の場合、それぞれのこまは動かされるたびに、
１のこまは常に左隣りのバーへ、２のこまは右隣り、
３のこまは左隣りのバーへ移っていることがわかる。
（左端と右端をつながったものとして捉えたとする。）

これは一般化でき、ｎ個のハノイの塔において、上からｍ番目のこまは、
ｎ＋ｍが奇数なら右隣のバーへ、偶数なら左隣のバーへ移動している。

またさらに、ステップ数を２進表示してみる。

step-000	step-001	step-010	step-011	step-100	step-101	step-110	step-111
[1] _I_ _I_ [2] _I_ _I_ [3] _I_ _I_	_L_ _I_ _I_ [2] _I_ _I_ [3] _I_ [1]	_L_ _L_ _I_ _L_ _L_ _I_ [3] [2] [1]	_L_ _L_ _I_ _L_ [1] _I_ [3] [2] _I_	_I_ _L_ _I_ _I_ [1] _I_ _I_ [2] [3]	_L_ _L_ _I_ _L_ _L_ _I_ [1] [2] [3]	_L_ _I_ _L_ _L_ _I_ [2] [1] _I_ [3]	_I_ _I_ [1] _I_ _I_ [2] _I_ _I_ [3]

そして、それぞれのステップにおいて、右側からビットを調べていくと、
最初に立っているビットの桁と動かすこまの番号が一致していることに気づく。

ステップ	step-000	step-001	step-010	step-011	step-100	step-101	step-110	step-111
最初に立ってる桁	nothing	2^1	2^2	2^1	2^3	2^1	2^2	2^1
実際の手順	[1] _I_ _I_ [2] _I_ _I_ [3] _I_ _I_	_L_ _I_ _I_ [2] _I_ _I_ [3] _I_ [1]	_L_ _L_ _I_ _L_ _L_ _I_ [3] [2] [1]	_L_ _L_ _I_ _L_ [1] _I_ [3] [2] _I_	_L_ _L_ _I_ _I_ [1] _I_ _I_ [2] [3]	_L_ _L_ _I_ _L_ _L_ _I_ [1] [2] [3]	_L_ _I_ _L_ _L_ _I_ [2] [1] _I_ [3]	_I_ _I_ [1] _I_ _I_ [2] _I_ _I_ [3]
動かしたこま	nothing	1	2	1	3	1	2	1

（各々のステップにおいて、右側からビットを調べて最初に立っている桁は、
２＾１−２＾２−２＾１−２＾３−２＾１−２＾２−２＾１である。
先の動かしたこまの順と比較。一致している。）

よって、ハノイの塔は再帰処理を用いることなく次の手順で解ける。
またこの方法はメモリを無駄に消費することもない。

step=1;
while (step<2^n)
右からstepのビットを調べる
ｍ番目のビットが立っていれば、ｍ番目のこまを（−１）＾（ｍ＋ｎ−１）方向へ動かす
step +=1;
end

---

こまがｎ個のときはｎ−１個のときの手順を二回繰り返すことと、その間に一番大きなこまを、
ただ一度動かすという新たな手順が一手増えるというのが、このゲームの法則です。
それをステップ数の2進数と対応させるというところが、このアルゴリズムの目玉なのですが、
いかがでしょうか。

---

同様のアルゴリズムを用い再帰処理なしに、ドラゴン曲線を描くプログラムをVisualC++で作りました。
Ｗｉｎ上で動くものです。ここ
許可なき転載禁止。
ご意見お待ちしております。 メールください。