ハノイの塔というのはパズルだが、リカージョンというアルゴリズムによくなじむのでプログラミングの教科書に出ていることがある。 自分がこれを見たのは”Oh Pascal!”というパスカルの入門書で30年くらい前に発行された学生向けの教科書だ。
パズルの内容はこんな具合。
１．3本の棒が立っている。仮にこれを右からA,B,Cとする。
２．Aには真ん中に穴のあいた円盤が積み上げてある。円盤の直径は底にあるものが一番大きく、上に行くほど小さくなる。
３．一度に一個ずつこのこの円盤を取り出して他の棒に移すことができる。最終的には全部の円盤をCに移したい。
４．ただし、大きな円盤を小さな円盤の上に置くことはできない。
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) =
if n>2 Move (n-1 disks from A to B using C)
Move a disk from A to C
if n>2 Move (n-1 disks from B to C using A)
このパタ-ンを使って関数を書くと、自分で自分自身を呼びだす関数になる。これがいわゆるRecursion と呼ばれるプログラムテクニックだがCでもPascalでもPHPでもいまどきのプログラムなら軒並みサポートされている。ただし普通のループに比べるとスタックにどんどん自分のコピーを積んでいくためメモリーを消費し、昔の8ビットパソコンでは何せRAMが32キロバイトあれば高級機、計算しているうちにメモリーが足りなくなる、なんてこともあったりして、Loopで記述できるものはRecursionをさける、というのが常識だった。
しかしながらこの記述の簡便さ、短さは感動ものである。今のパソコンはそんなにメモリを気にしなくてもよいので、改めて組んでみよう。
上のパターンは条件判定を何度も呼ぶことになるので少し工夫して
function Move (n, from, to , using) =
if n=1 "Move a Disk from 'from' to 'to'"
else
Move (n-1,from, using,to)
"Move a Disk from 'from' to 'to'"
Move (n-1,using, to, from)
というようなロジックを使うこととし、
Free Pascalで書いた例
program hanoi;
{Recursively solve the towers of Hanoi problem. Moves disks from A to C.
The code from "Oh Pascal" by Doug Cooper}
var height:integer;
procedure Move (Height: integer; FromPeg,ToPeg,UsingPeg:char);
begin
if Height = 1
then writeln('Move disk from ', FromPeg,' to ',ToPeg)
else begin
Move (Height-1, FromPeg,UsingPeg,ToPeg);
writeln('Move a disk from ',FromPeg,' to ',ToPeg);
Move (Height-1,UsingPeg,ToPeg,FromPeg)
end;
end;
begin
writeln('How Many disks are you going to start with?');
readln(Height);
Move (Height,'A','C','B');
readln()
end.
C++で書いた例
#include < iostream >
using namespace std;
void move(int numberOfDisk, char fromPin,char toPin,char usePin);
int main() {
int numberOfDisk;
char fromPin = 'A',usePin='B',toPin='C';
cout << "How many disk do you want to move from pin A to pin C?: " ;
cin >> numberOfDisk;
move (numberOfDisk,fromPin,toPin,usePin);
return 0;
}
void move(int numberOfDisk, char fromPin,char toPin,char usePin) {
if(numberOfDisk == 1) cout << "Move a Disk from "<< fromPin << " to " << toPin<< endl;
else {
move(numberOfDisk-1,fromPin,usePin,toPin);
cout << "Move a Disk from " << fromPin << " to " << toPin << endl;
move(numberOfDisk-1,usePin,toPin,fromPin);
}
}
Pythonで書いた例
'''Towers of Hanoi'''
def move(numberOfDisk, fromPin, toPin, usingPin):
if (numberOfDisk == 1):
print ("Move a Disk from ",fromPin," to ",toPin)
else:
move(numberOfDisk-1,fromPin,usingPin,toPin)
print ("Move a Disk from ",fromPin," to ",toPin)
move(numberOfDisk-1,usingPin,toPin,fromPin)
if __name__ == '__main__':
numberOfDisk = input("How many Disk would you like to move? ")
move(int(numberOfDisk),'A','B','C')
Python で円盤の数を4とした場合の実行例
~ $ python3 hanoi.py
How many Disk would you like to move? 4
Move a Disk from A to C
Move a Disk from A to B
Move a Disk from C to B
Move a Disk from A to C
Move a Disk from B to A
Move a Disk from B to C
Move a Disk from A to C
Move a Disk from A to B
Move a Disk from C to B
Move a Disk from C to A
Move a Disk from B to A
Move a Disk from C to B
Move a Disk from A to C
Move a Disk from A to B
Move a Disk from C to B
動かす回数は円盤の数が1の時は1、2の時は3、3の時は7、4の時は上の出力のように15となり、円盤の数がｎのときは
2のｎ乗から１を引いた値
となる。枚数が多ければ多いほど全部のステップの数がどんどん大きくなっていく。
Python version で試してみると、手持ちのややくたびれたノートブックパソコンではステップの出力が終わるのに 円盤の数が23枚で30秒、24枚で1分、25枚で2分かかった。（下の出力結果参照）実行時間がここの調子で倍々で増えていくとすると入力が64枚のときに解法を出力するのに2の38乗の分がかかるということになるが、これを年に直すと、なんと52万年というとんでもない数字になる。 ので上のプログラムに64と入力しようものなら計算が終わらない。 なるほど、これでは世界が滅びるわけだ。
~ $ time echo 23 | python3 hanoi.py >/dev/null
real 0m29.308s
user 0m29.225s
sys 0m0.054s
~ $ time echo 24 | python3 hanoi.py>/dev/null
real 0m58.437s
user 0m58.237s
sys 0m0.122s
~ $ time echo 25 | python3 hanoi.py>/dev/null
real 1m55.068s
user 1m54.540s
sys 0m0.320s
