ハノイの塔を解く(Solving Towers of Hanoi)

ハノイの塔というのはパズルだが、リカージョンというアルゴリズムによくなじむのでプログラミングの教科書に出ていることがある。 自分がこれを見たのは”Oh Pascal!”というパスカルの入門書で30年くらい前に発行された学生向けの教科書だ。 パズルの内容はこんな具合。 1.3本の棒が立っている。仮にこれを右からA,B,Cとする。 2.Aには真ん中に穴のあいた円盤が積み上げてある。円盤の直径は底にあるものが一番大きく、上に行くほど小さくなる。 3.一度に一個ずつこのこの円盤を取り出して他の棒に移すことができる。最終的には全部の円盤をCに移したい。 4.ただし、大きな円盤を小さな円盤の上に置くことはできない。 Hanoiの塔というのはこの”金の”円盤を64枚積み上げたものだそうで、このパズルが解けたときには世の中が終焉を迎える、というオトロしい落ちがついている。 これをコンピュータープログラムを使って解くとどうなるか、という話である。 パターンを見つけるために少ない枚数で実際に解くことを試みる。 Disk(円盤)の数が一枚の時には簡単だ。円盤をAからCに移せばよい。 Move(1disk from A to C) = Move a Disk from A to C では2枚の時にはどうなるか Move(2disks from A to C) = Move a Disk from A to B Move a Disk from A to C Move a Disk from B to C ここで棒Bを使うことになる。 つまり、まず上の円盤を棒AからBに移し、下の円盤をAからCへ、最後にBに移してあった円盤をCに移して完成だ。 Move (2 disks from A to C) = Move (2 disks from A to C using B) 3枚はどうか。 すでに2枚を動かす方法はわかっているのその方法を使ってまずは2枚をBに動かしておき、最後の一枚をAからCに移動、さらに2枚を動かす方法を使ってBからCに移動するという方法で動かせる。 Move(3 disks from A to C using B) = Move(2 disks from A to B using C) Move a disk from A to C Move (2 disks from B to c using A) 4枚の場合も同様に考えられるのでパターンとしては (n-1)枚の円盤をAからBに移す。最後の円盤をAからCに移動し、その後(n-1)枚の円盤をBからCに移す。 ということになる。 Move (n disks from A to C using B) […]