ハノイの塔を解く(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) […]

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 という方法も述べてある(小さなプロジェクトではこちらのほうが早いとある)のだが、自分の環境ではうまくできなかった。