0371.blog

最大公約数を求めるユークリッドの互除法(GCM)

code

こんにちは、0371です。

今回は、ユークリッドの互除法について書いていきます。
基本情報技術者試験のアルゴリズムの問題集から、擬似言語の問題を実際の言語でプログラミングしてみました。

ユークリッドの互除法 とは

二つの整数の大きい数値から小さい数値を引き続け、両者が等しくなるまで繰り返す。
等しくなった値が最大公約数。

GCMは、Greatest Common Measure(最大公約数)の頭文字が由来になっている。

コード

今回は、二つの整数から最大公約数を求めます。 言語はJavaです。

main関数内の変数 ab に好きな数値を当てはめてください。
int型の最大値は、2147483647 2の31乗なので、それよりも下の数値にしましょう。

※なぜ32ではなく31乗なのかというと、最上位のビット(左端のビット)は符号ビットとして使われているためです。
2の補数で表すと、0は+、1は-となります。

Main.java

public class Main {

    public static void main(String[] args) {
        int a = 84; // ここに好きな数値をいれる
        int b = 24; // ここに好きな数値をいれる
        System.out.println(a+" と "+b+" の最大公約数は "+GCP(a,b));
    }

    private static int GCP(int a, int b) {
        int count = 0; // 確認用
        while(a != b) {
            count++; // 確認用
            System.out.println(count+"回目の処理"); // 確認用
            
            if(a > b) {
                System.out.println("a = "+a+ " - " +b); // 確認用
                a = a - b;
            } else {
                System.out.println("b = "+b+ " - " +a); // 確認用
                b = b - a;
            }

            System.out.println("a = "+a); // 確認用
            System.out.println("b = "+b); // 確認用
            System.out.println(); // 確認用
        }
        return a;
    }
}

確認用とコメントしている行は、削除しても構いません。
トレースする場合はそのまま実行してください。

上記の設定した数値で実行すると、以下のような結果が表示されます。

1回目の処理
a = 84 - 24
a = 60
b = 24

2回目の処理
a = 60 - 24
a = 36
b = 24

3回目の処理
a = 36 - 24
a = 12
b = 24

4回目の処理
b = 24 - 12
a = 12
b = 12
84 と 24 の最大公約数は 12

ちなみに、whileループではなく、再帰処理で記述した場合はこうなります。

Main.java

public class Main {

    public static void main(String[] args) {
        int a = 84;
        int b = 24;
        System.out.println(a+" と "+b+" の最大公約数は "+GCP(a,b));
    }

    private static int GCP(int a, int b) {

        if(a > b) {
            a = a - b;
        } else {
            b = b - a;
        }

        if(a != b) {
            return GCP(a,b);
        }
        return a;
    }
}

結果は一つ目のコードと同じです。

今日の一言

アルゴリズム、わからん。