ハノイの塔の解き方は実質的な解き方(再帰的方法)の他、2進法で解析する方法と、グレイコードによる解法がある。
【2進法で解析】
初期状態からn回動かした状態は、nの2進数表記から、一意的に求めることができる。
・nを2進数で書き表す。
・最上位が一番大きい円盤、以下順に対応する。
1の位が一番小さい円盤に対応する。
・最上位が0のとき、一番大きい円盤はまだ動いていない。
1の時には移動済みである。
・各桁の数字を一つ上の位と比べる。
2進数の演算を利用すると、n番目の移動を簡単に表記することができる。C言語の表記を用いるとn番目の移動は、「(n&(n-1))%3番目の棒にある円盤を((n|(n-1))-1)%3番目の棒に移動する」となる。
【グレイコードによる解法】
ハノイの塔の解答とグレイ・コードによる数字の表記は近い位置にある。
グレイコードによって表記された数字の一番下の桁に一番小さい円盤、次の数字に二番目の円盤というようにすべての桁と円盤を対応付けたとき、数字が変化することによって変わるビットに対応する円盤を動かすことで解答が求められる。
この方法では動かす円盤が分かるだけでどの棒に動かすべきかは求められないが、円盤同士のパリティを考えることにより移動先も定まる。(偶数番目同士、奇数番目同士の円盤は重ならない)
【由来】
ハノイの塔は、フランスの数学者E・リュカ(Edouard Lucas)が1883年に考えたものである。リュカは、インドに次のような伝説があると説明している。
『ブラフマーの塔』
インドのガンジス河の畔のベナレス(ヴァラナシ)に世界の中心を表すという聖堂がある。
そこには3本の大理石の柱(ダイヤモンドの針との説もあり)が立てられており、そのうちの1本には、当初64枚の黄金の円盤が大きい円盤から順に重ねられていたという。バラモン僧たちはそこで、一日中円盤を別の柱に移し替える作業を行っている。そして、全ての円盤の移し替えが終わったときに、この世は崩壊し終焉を迎えると言われている。
もちろんこれはリュカの作り話であるが、1枚移動させるのに1秒かかったとして、64枚の円盤を移動させるには、最短でも約5,845億年かかる。
もう少し詳しく知りたい方はコチラへ行ってみるとよろしいかと思います。
フリー百科事典『ウィキペディア(Wikipedia)』