ハノイの塔
再帰的でない解き方として、以下のような手順がある。人間が解く場合にも利用可能である。
いちばん小さい円盤とそれ以外の円盤を交互に動かす。
いちばん小さい円盤は常にB→C→A→B(nが偶数の場合)またはC→B→A→C(nが奇数の場合)の順に動かす。
いちばん小さな円盤以外の円盤を動かす場面では、動かせる方法は1通りしかない。
このような単純なアルゴリズムで表記されるにもかかわらず、実際には 2 − 1 手かかる。
棒が4本以上の場合の最小手数は三角数を用いて計算できることが知られている。
3本の棒にA,B,Cの名前を付ける。最初Aに n 個の円盤があり、Cにすべての円盤を移動させるとすると、次のようにする。n = 1のときは自明であるから、n > 1の場合、
上から n − 1 個目までの円盤を何らかの方法でAからBに移動する。
残った1枚をAからCに移動する。
Bにある円盤を何らかの方法でBからCに移動する。
ここで、1は最初Aに n − 1 個の円盤があり、Bにすべての円盤を移動させるという問題ととらえることができる。そこで、次のようにする。
上から n − 2 個目までの円盤を何らかの方法でAからCに移動する。
残った1枚をAからBに移動する。
Cにある円盤を何らかの方法でCからBに移動する。
3も同様にして行うことができ、「何らかの方法」の部分を分解していくと解ける。
ハノイの塔の解答とグレイ・コードによる数字の表記は近い位置にある。
グレイコードによって表記された数字の一番下の桁に一番小さい円盤、次の数字に二番目の円盤というようにすべての桁と円盤を対応付けたとき、数字が変化することによって変わるビットに対応する円盤を動かすことで解答が求められる。
この方法では動かす円盤がわかるだけでどの棒に動かすべきかは求められないが、円盤同士のパリティを考えることにより移動先も定まる(偶数番目同士、奇数番目同士の円盤は重ならない)。
前述の通り、全ての桁と円盤を対応付ける事は、その桁に対応したメルセンヌ数に支配される事と等しい。