Java でハノイの塔をプログラミングしてみました。

再帰アルゴリズムでググるとほとんどの言語でサンプルがあります。

しかし、再帰アルゴリズムは理屈では理解できても実際に使おうとすると難しいものです。

そこで NetBeans を使って再帰アルゴリズムの仕組みをみていこうと思います。

まず、ハノイの塔についておさらいしておきましょう。

Wikipedia によると、ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発売したゲーム『ハノイの塔』がルーツである。

その内容は下記のようになっている。

インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。

そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。

そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。

これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し替えのルールの説明は省略）。

そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。

n 枚の円盤すべてを移動させるには最低 2^n-1 回(2のｎ乗 – 1 回)の手数がかかります。

なんか恐ろしいですね。

それにハノイの塔じゃなくてブラフマーの塔になってます。（ なんでだろう？ )

さて。肝心の移し替えのルールをザックリと確認しましょう。

移し替えの際、円盤は一回に一枚しか移し替えできない。

小さな円盤の上に大きな円盤を重ね置くことはできない。

実にシンプルなルールですね。

しかし、シンプルだからといって侮れません。

考え方としては円盤の枚数を n 枚とします。

そして円盤が重ね置いてあるダイヤの針は左( LEFT )とします。

移し替え先のダイヤの針は右( RIGHT )、そして移し替え作業用のダイヤの針を中央( CENTER )とします。

まず、n -1 枚の円盤を中央のダイヤの針に移し替えます。

そして、右のダイヤの針に左のダイヤの針に残っている一番大きな円盤( n 枚目の円盤 )を移し替えます。

次に中央のダイヤの針に移し替えられた n-1 枚の円盤を左のダイヤの針に移し替えます。

言葉よりプログラムの流れで確認したほうが理解し易いかもしれませんね。

上記の考え方を再帰アルゴリズムを利用して組んだコードがこれです。

素人が作ったプログラムなので読みにくいとは思いますがじっくりプログラムの流れを確認してください。

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

Java でユークリッドの互除法　Euclidean Algorithm をプログラミングしてみました。

再帰アルゴリズムを使ってます。

再帰アルゴリズムについてはこちらで簡単な覚え書きを残してあります。

再帰アルゴリズム　その１

再帰アルゴリズム　その２

ユークリッドの互除法とはいったいどんな仕組みなのか調べてみました。

ある二つの自然数の最大公約数を求めるのに非常に優れた方法らしいです。

名前に互除法とあるとおり互いに割り算を行って解を導き出す方法です。

簡単に説明すると自然数 r1 と r 2 ( r1 >= r2 ) の最大公約数を求めるとき ( 注意 : r の後の数字と n は小さい数字だと思ってください。)

r1 / r2 の余り r3 を求める。

次に r2 / r3 の余り r4 を・・・

これを rn が 0 になるまで繰り返す。

この時、 r(n-1) が最大公約数となる。

実にシンプルです。

数学的証明はここでは割愛させていただきます。

これを Java プログラムにするには再帰アルゴリズムを使えば簡単にできそうですね。

さっそく作ってみましょう。

package euclidean_algorithm;

/**
 *
 * @author Yucchi
 */
public class Euclidean_Algorithm {

    public static void main(String[] args) {
        if (args.length != 2) {
            System.err.println("えらー (゜´Д｀゜) 自然数を二つ入力してね。");
            System.exit(0);
        }

        int x = java.lang.Integer.parseInt(args[0]);
        int y = java.lang.Integer.parseInt(args[1]);

        if (x < 0 || y < 0) {
            System.err.println("えらー (゜´Д｀゜) 自然数を二つ入力してね。");
            System.exit(0);
        }
        
        if (x < y) {
            y ^= x;
            x ^= y;
            y ^= x;
        }
        
        System.out.println(args[0] + " と " + args[1] + " の最大公約数は " + gcd(x, y) + " だよね。");
        
    }

    private static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
}

非常にシンプルで解りやすいですね。

せっかくだからデバッグ実行させてプルグラムの流れを確認してみよう。

変数 x , y の値に注目です。

main() メソッドの引数二つを整数とし、大きさを比較し計算処理のため必要に応じて値を入れ替え、

再帰メソッドで答えが出るまで(再帰のループから抜ける条件になるまで）ひたすらぐるぐる回るってかんじ。

ユークリッドの互除法ってシンプルだけど良く考えられた素晴らしいものですね。

最後にすでにお気付きの方もいると思うのですが上記プログラムはちょっと手抜きの部分があります。

目的がユークリッドの互除法を試してみるということなのでご容赦のほどを(^_^;

ちなみに java.lang.NumberFormatException が・・・・・・です。（本当は忘れていたことは内緒です）