目次> 第20章> 20.2 | TOPUPPREVNEXT |
リカーシブ・プログラムの例として、定番の「ハノイの塔」を紹介します。
[ハノイの塔]
移動の手順 | 円盤の状態 |
---|---|
初期状態 | |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 |
「棒Aから棒Bへ移す」というアルゴリズムは、 どう書けばよいのでしょう。
円盤がN枚あったとして
|
N枚を移すという問題が、 N−1枚を移すという(少し簡単な)問題と、 1枚を動かすという簡単な動作の組み合わせで表現できました。 Nが0の時は、「なにもしない」ときめれば、アルゴリズムが完成です。
メソッドの書き方で記述すると、 [ 棒a から 棒b へ 棒c を使って n枚 移す 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);
}
}
実行結果
以上で、本題(リカーシブ・アルゴリズムの例)は終わりです。
お急ぎのかたは 次節 20.3 に進んでください。
せっかくですから、円盤の動く様子を表示するプログラムにしてみましょう。
この節の最後の実行中の画面(20.2.4)を見て、
イメージがつかめたら、次項(20.2.2)に進んでください。
要件定義をしっかりやりたい場合は、こちらを経由しましょう。
問題を素直にとらえて、棒 Pole クラス と 円盤 Disk クラスを定義しましょう。 この他に、棒や円盤を表示するパネル ViewPanel クラスと、 全体をまとめあげる Hanoi クラスを用意します。
Pole クラスは、棒にさされた円盤をおぼえておきます。
棒に最大いくつの円盤をさすかを指定して、棒を生成することにします。
Pole クラスに必要なメソッドは、
Disk クラスは、円盤の大きさと色ぐらいを保存しておけばよいと思います。
棒や円盤の様子を表示する ViewPanel クラスを用意し描画をおこないます。 必要なメソッドは、
実際の描画は、ViewPanel クラスの (親クラス JPanel から継承した) repaint メソッドを呼び出します。
あとは、棒や円盤を生成したり、
20.2.1項 で紹介した shift メソッドで円盤を動かしたり、
表示速度を調節するボタンを処理したりする Hanoi クラスを考えれば終わりです。
shift メソッド の実装を、 Pole クラス と Hanoi クラス のいずれで行うか
意見の分かれるところですが、
64枚の円盤を移し終わると この世の終わりが来るということなので、 MAXDISK は 31 にしておきます。
全体は BorderLayout で、表示用パネルを CENTER に、 表示を制御する部分部分は SOUTH にまとめました。
SOUTH のパネルは GridBagLayout の例題にもなっています。 パネルの設計およびコーディング手順は、 Appendix F GridBagLayout の【例2】 を参照してください。
更新日:2006-02-09 | TOPUPPREVNEXT |