ハノイの塔

ハノイの塔 †

3本の杭と中央に穴の開いた円盤を左端の杭から右端の杭へ移動させるパズル。円盤は下から上へと大きい順に重ねられている。小さい円盤の上に大きい円盤を置いてはいけない。これを最短手数で行った場合、n枚の円盤を移動させるのに2^n-1回の手数がかかる。

1枚の円盤を移動させるのに必要な手数は1回。2枚を移動させる場合は一番上の小さい円盤をどかしてから下の大きい円盤を右端の杭に移動させるため3回かかる。3枚の場合は上の2枚をどかしてから一番下の大きい円盤を右端の杭に移動させ2枚を右端に移動させるため、2枚移動させるのにかかった手数と一番大きな円盤を移動させる1回、そして再び2枚移動させるのにかかった手数の計7回がかかる。同様に4回の場合は上の3枚をどかして一番下を右端に移動し、また3枚を移動させるので15回の手数がかかる。
つまり、n枚を移動させるにはn-1枚を移動し、一番大きな1枚を右端へ動かし、再びn-1枚を動かすので2×(n-1を動かす手数)+1回の手数がかかる。 n枚の手数をa(n)とすると、a(n)=2a(n-1)+1ということで、これからa(n)=2^n-1が導ける。
枚数手数

1 1

2 3

3 7

4 15

5 31

6 63

7 127

【奇数手目】1番小さい円盤を、偶数番目(0番目含む)の大きさの円盤の上に移動させる。　0番目と0以外の偶数番目の大きさのものがあった場合は0番目以外の方に移動させる。
【偶数手目】1番小さい円盤以外の2つの杭のうち動かせる方の円盤を移動させる。
第一手　1番小さい円盤を移動させるが
- 円盤の数が奇数の場合、右側の杭へ、
- 円盤の数が偶数の場合、真ん中の杭へ移動させる。