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 が・・・・・・です。（本当は忘れていたことは内緒です）

再帰アルゴリズムの覚え書きの続きです。

再帰アルゴリズム　その１

今回も、非効率的かつ非現実的な例題を利用して再帰アルゴリズムを理解していきましょう。

今回はフィボナッチ数列の特定項の値を求めるプログラムです。

フィボナッチ数列とは簡単に説明すると

F1 = 1

F2 = 1

F3 = 2

　　・
　　・
　　・

Fn = F(n – 2) + F(n – 1)

ただし、n = 1 または n = 2 のとき F(n) = 1 となる数列のことである。

つまり、1, 1, 2, 3, 5, 8, … と続く数列で、 隣り合う2つの数を足し算すると、その上位の数になる数列です。

参考までに、フィボナッチ数は、ちょうど８００年前に刊行された「算盤の書」（１２０２年）の中の有名な「兎の問題」から生まれました。

これをプログラムにするにはどうしたらいいでしょうか？

数学的手法でいくか？ループ文で和を取り値を入れ替えながら？

面倒なのでここは再帰アルゴリズムを使いましょう。(^_^;

計算処理負荷が非常に大きいことは秘密にしておきましょう。（ヲヒ

とりあえずサクッと作ってみたのでデバッグ実行させてプログラムの流れを確認してみましょう。

package jp.yucchi.fibonacci.number;

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

    private static final int TARGET = 5;
    private static int ans;

    public static void main(String[] args) {
        ans = fib(TARGET);
        System.out.println("フィボナッチ数列第 " + TARGET + " は " + ans + " です。");
    }

    private static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        } else {
            ans = fib(n - 2) + fib(n - 1);
            return ans;
        }

    }
}

上記のプログラムをデバッグ実行させます。

変数、n , ans の値、再帰呼び出し及び処理から戻ってくる時のプログラムの流れをしっかり確認してくださいませ。

しっかり確認できましたでしょうか？

概略図を作って流れを考察してみます。

fib(5) から fib(5 – 2) そして fib(3 – 2)

処理を終え fib(5 – 2) に戻り次の fib(3 –1)

処理を終え fib(5 – 2) に戻り fib(5 – 2) の処理を終え fib(5) に戻る

そして fib(5 –1) へ、そして fib(4 – 2) へ、処理を終えて fib(5 – 1) へ戻る

次の fib(4 – 1)　へ、そして fib(3 – 2) へ、処理を終えて fib(4 – 1) へ戻る

そして fib(3 – 1) へ、処理を終えて fib(4 – 1) へ戻る、処理を終えて fib(5 – 1) へ戻る、処理を終えて fib(5) に戻る

これでやっと呼び出し元に計算処理を結果を返せるって仕組みです。

あ～、しんど　(~_~;)

再帰アルゴリズムってプログラムだとシンプルだけど流れを考えるとしんどいですね。

えっ？私だけ？

まぁ、いいか。

ちなみに再帰アルゴリズム使わないプログラムは下記のようになります。

package jp.yucchi.fibonacci.number2;

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

    private static final int TARGET = 5;

    public static void main(String[] args) {
        System.out.println("フィボナッチ数列第 " + TARGET + " は " + fib(TARGET) + " です。");
    }

    private static int fib(int n) {
        int x = 1;
        int y = 1;
        for (int i = 2; i < TARGET; i++) {
            int z = x + y;
            y = x;
            x = z;
        }
        return x;
    }
}

さて、どちらが効率いいですか？