ハノイの塔 Tower of Hanoi
Java でハノイの塔をプログラミングしてみました。
再帰アルゴリズムでググるとほとんどの言語でサンプルがあります。
しかし、再帰アルゴリズムは理屈では理解できても実際に使おうとすると難しいものです。
そこで NetBeans を使って再帰アルゴリズムの仕組みをみていこうと思います。
まず、ハノイの塔についておさらいしておきましょう。
Wikipedia によると、ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発売したゲーム『ハノイの塔』がルーツである。
その内容は下記のようになっている。
インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。
そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。
そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。
これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し替えのルールの説明は省略）。
そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。
n 枚の円盤すべてを移動させるには最低 2^n-1 回(2のｎ乗 – 1 回)の手数がかかります。
なんか恐ろしいですね。
それにハノイの塔じゃなくてブラフマーの塔になってます。（ なんでだろう？ )
さて。肝心の移し替えのルールをザックリと確認しましょう。
移し替えの際、円盤は一回に一枚しか移し替えできない。
小さな円盤の上に大きな円盤を重ね置くことはできない。
実にシンプルなルールですね。
しかし、シンプルだからといって侮れません。
考え方としては円盤の枚数を n 枚とします。
そして円盤が重ね置いてあるダイヤの針は左( LEFT )とします。
移し替え先のダイヤの針は右( RIGHT )、そして移し替え作業用のダイヤの針を中央( CENTER )とします。
まず、n -1 枚の円盤を中央のダイヤの針に移し替えます。
そして、右のダイヤの針に左のダイヤの針に残っている一番大きな円盤( n 枚目の円盤 )を移し替えます。
次に中央のダイヤの針に移し替えられた n-1 枚の円盤を左のダイヤの針に移し替えます。
言葉よりプログラムの流れで確認したほうが理解し易いかもしれませんね。
上記の考え方を再帰アルゴリズムを利用して組んだコードがこれです。
素人が作ったプログラムなので読みにくいとは思いますがじっくりプログラムの流れを確認してください。
| yucchi.jp.hanoi.Hanoi.java |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
package yucchi.jp.hanoi; /** * * @author Yucchi */ public class Hanoi { private static int count; private static int TARGET_NUMBER = 3; // ハノイの塔 // n : 移動させる円盤の枚数 // from : 移動元の塔 // work : 作業用の塔 ---> 一番下の円盤以外の一時的な置き場所 // dest : 移動先の塔 private static void hanoi(int n, String from, String work, String dest) { if (n > 0) { // n - 1 番目の輪を LEFT から CENTER に移動させる。 hanoi(n - 1, from, dest, work); // 上の hanoi(n - 1, from, dest, work)を実行完了後に // n 番目の円盤を移動させる。 System.out.println(++count + " ： " + n + "番目の円盤を" + from + "から" + dest + "へ移動させる。"); // 上の hanoi(n - 1, from, dest, work) メソッドで // 一番下以外の棒がfromからworkに移っているので、 // 今度は work を from にして、空いた from を work にして移動させる。 // n - 1 番目の輪を CENTER から LEFT に移動させる。 hanoi(n - 1, work, from, dest); } } public static void main(String[] args) { System.out.println(TARGET_NUMBER + "枚のハノイの塔 開始"); // ダイアでできた LEFT 塔にある TARGET_NUMBER 枚の純金の円盤をダイアでできた RIGHT 塔に移動させる。 hanoi(TARGET_NUMBER, "LEFT", "CENTER", "RIGHT"); System.out.println(TARGET_NUMBER + "枚のハノイの塔 終了"); } } |
どうでしょうか？
理解できましたでしょうか？
考え方は非常にシンプルだけどけっこう流れは追っていくと複雑に感じますね。
いちおう参考までにこれも貼っておきます。
hanoi メソッドが再帰的に実行されているのが確認できます。
これで再帰アルゴリズムで複雑な繰り返し処理を記述できるようになったとはとても思えないけど
ちょっとは再帰アルゴリズムの使いどころを理解したつもりになりました。
たぶん、すぐに忘れてしまうだろうけどまた挑戦してみたらいいだけのことだし。
気楽に楽しんでいこう！ (*^o^*)
再帰アルゴリズムについてはこちらで簡単な覚え書きを残してあります。
ユークリッドの互除法 Euclidean Algorithm
TAGS: Java | 2013年1月4日5:03 AM
Comment
ゆっちのBlog » Nクイーン問題 nQueens Problem
Trackback
2013年4月24日9:55 PM（編集）
[...] ハノイの塔 Tower of Hanoi [...]
Trackback URL