目次> 第20章> 20.2 TOPUPPREVNEXT

20.2 ハノイの塔

リカーシブ・プログラムの例として、定番の「ハノイの塔」を紹介します。

[ハノイの塔]

地面に3本の棒A、B、Cが立っています。 棒Aには、中心に穴のあいた円盤が64枚さしてあります。 円盤の大きさはすべて異なっていて、大きいものが下、小さいものが上に、 順番にさしてあります。 次の3つの規則をまもって、 この64枚の円盤を棒Aから棒Bに移しなさい、というのがハノイの塔の問題です。
1)一回に1枚だけしか動かしてはいけない。
2)棒以外の場所においてはいけない。
3)小さい円盤の上に大きい円盤を重ねてはいけない。

 20.2.1 アルゴリズム

円盤が3枚のケースで実際に移動させてみましょう。
円盤が重なった絵がうまくかけないので、横から見た図で我慢してください。

移動の手順 円盤の状態
初期状態
 1 
 2 
 3 
 4 
 5 
 6 
 7 

「棒Aから棒Bへ移す」というアルゴリズムは、 どう書けばよいのでしょう。

円盤がN枚あったとして

  1. N−1枚をAからCへ移す        
  2. N枚目をAからBへ動かす
  3. N−1枚をCからBへ移す

N枚を移すという問題が、 N−1枚を移すという(少し簡単な)問題と、 1枚を動かすという簡単な動作の組み合わせで表現できました。 Nが0の時は、「なにもしない」ときめれば、アルゴリズムが完成です。

メソッドの書き方で記述すると、 [ 棒 から 棒 へ 棒 を使って 枚 移す shift ] は 以下のようになります。

static void shift(char a, char b, char c, int n) {
    if(n==0) {
        return;
    }
    else {
        shift(a, c, b, n-1);
        movecount++;
        System.out.println(movecount + ".  move from [" +
                           a + "] to [" + b + "]");
        shift(c, b, a, n-1);
    }
}
とりあえず、このアルゴリズムが動くことを確かめてみましょう。
ソースプログラムは HanoiX.java にあります。コンパイルして実行してみてください。 読めば解ると思いますが、円盤数をコマンドラインで与えるようになっています。

実行結果

以上で、本題(リカーシブ・アルゴリズムの例)は終わりです。 お急ぎのかたは 次節 20.3 に進んでください。
せっかくですから、円盤の動く様子を表示するプログラムにしてみましょう。 この節の最後の実行中の画面(20.2.4)を見て、 イメージがつかめたら、次項(20.2.2)に進んでください。 要件定義をしっかりやりたい場合は、こちらを経由しましょう。

 20.2.2 クラス設計

問題を素直にとらえて、棒 Pole クラス と 円盤 Disk クラスを定義しましょう。 この他に、棒や円盤を表示するパネル ViewPanel クラスと、 全体をまとめあげる Hanoi クラスを用意します。

Pole クラスは、棒にさされた円盤をおぼえておきます。
棒に最大いくつの円盤をさすかを指定して、棒を生成することにします。 Pole クラスに必要なメソッドは、

です。

Disk クラスは、円盤の大きさと色ぐらいを保存しておけばよいと思います。

棒や円盤の様子を表示する ViewPanel クラスを用意し描画をおこないます。 必要なメソッドは、

実際の描画は、ViewPanel クラスの (親クラス JPanel から継承した) repaint メソッドを呼び出します。

あとは、棒や円盤を生成したり、 20.2.1項 で紹介した shift メソッドで円盤を動かしたり、 表示速度を調節するボタンを処理したりする Hanoi クラスを考えれば終わりです。
shift メソッド の実装を、 Pole クラス と Hanoi クラス のいずれで行うか 意見の分かれるところですが、

自由に動かせる円盤と、円盤を保持するための棒があって、
円盤を動かしたり、必要な場合に再表示したりという制御は、 Hanoi クラスが受け持つ
というコンセプトにしました。

64枚の円盤を移し終わると この世の終わりが来るということなので、 MAXDISK は 31 にしておきます。

 20.2.3 画面の設計

全体は BorderLayout で、表示用パネルを CENTER に、 表示を制御する部分部分は SOUTH にまとめました。

SOUTH のパネルは GridBagLayout の例題にもなっています。 パネルの設計およびコーディング手順は、 Appendix F GridBagLayout の【例2】 を参照してください。

 20.2.4 プログラムの作成

ソースプログラムは、 Hanoi.java です。

実行中の画面
Hanoi-1.gif

J2SE 1.4/5.0用実行可能jarファイル Hanoi.jar


更新日:2006-02-09 TOPUPPREVNEXT