Aritalab:Lecture/Algorithm/Towers of Hanoi

ハノイの塔

(E. リュカ, 1883) 台の上に３本の棒が固定されており、一番左の棒をＡ、真ん中の棒をＢ、一番右の棒をＣとする。Ａにはn枚の円盤がはまっており、円盤は下へいくほど半径が大きくなっている。次のルールに従い、棒Ｂを利用して全ての円盤をＡからＣに移すとき、何回の移動が必要になるか。

1. 一回に一枚の円盤しか動かしてはいけない。
2. 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。）

解

n (>0) 枚の円盤�を移動する手数を��T_nと書く。上からn-1枚の円盤をまずBの棒に移し、一番大きい円盤をCに移してから、Bにあるn-1枚をもう一度全てCに移せばよいので、以下の漸化式を得る。

• T₀ = 0
• T_n = 2 T_n-1 + 1

ここでS_n = T_n/2ⁿとおく。

• S₀ = 0
• S_n = S_n-1 + 2^-n (n > 0)

この漸化式を解くと

S_n = 2^-1 + 2^-2 + ... 2^-n = 1 - 2^-n

従って Tⁿ = 2ⁿS_n = 2ⁿ-1となる。