ハノイの塔を解く(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) =
 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となり、円盤の数がnのときは

2のn乗から1を引いた値

となる。枚数が多ければ多いほど全部のステップの数がどんどん大きくなっていく。
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

NetBeans でクロスプラットフォーム開発環境を作る

BBBやRasPiで使うC/C++のプログラムをWindows上のNetBeans IDE で開発してしまおう、という話。 NetBeansはもともとJavaの開発環境だが、plugin で c/c++ もサポートしている。自分のようにWeekend hoby でプログラミングをやっているものにとってはAutocomplete やSyntax check、変数の使用状況のチェックなどを自動的にやって間違いを指摘してくれるeditor というのは重宝する。
こちらに、Eclipseを使ったアプリケーションの開発及びクロスコンパイルの方法を説明したビデオがあったので、NetBeansを使って同じようなことができないか調べてみた。

リソースの乏しいRasPi上ではなく、普通のデスクトップコンピューターでIDEを使ったアプリケーション開発を行い、コードの生成だけはRasPi上で行う。という環境を作りたかったわけだが、NetBeans.orgにちゃんとやり方の説明が載っていた。

設定は以外と簡単にできた。  Netbeans からLinux BoxにSSHで接続し、さらにLinuxBox からはSambaを使ってLinuxのfile system をWindows側にネットワークドライブとしてシェア、 netbeans のプロジェクトをこのシェアされたフォルダーに書き込んでいき、デバッグはLinuxBox側から行う。 設定さえきちんとできれば、すべてWindows上のnetbeans IDEから処理できる。
この場合、gcc, make, gdbなどのツールはlinuxbox 上に存在するものがsshを使って操作される。よって、こられのツールがLinux側にインストールされている必要があるが、きちんとインストールされていれば、設定の途中でnetbeansがちゃんと検出してくれる。
Linux Box 側からは以下の下準備が必要
1.Sambaのインストール及びsmb.configの設定。(sudo apt-get install samba samba-common-bin)
2.SSH (RasPiもBBBも初期設定でインストール済み)
3.g++, gcc, make, gdb のインストール(sudo apt-get install g++ gcc make gdb)

詳細はこのヘルプページの解説に従えばよい。 Sambaを使ってFolder を Shareする方法のほかにファイルの作成管理はWindows側で行って、コンパイル時にLinux側にすべてコピーするscpを使ったautomatic copy という方法も述べてある(小さなプロジェクトではこちらのほうが早いとある)のだが、自分の環境ではうまくできなかった。