最大公約数を求めるユークリッドの互除法（GCM）
2020-08-26
こんにちは、0371です。
今回は、ユークリッドの互除法について書いていきます。
基本情報技術者試験のアルゴリズムの問題集から、擬似言語の問題を実際の言語でプログラミングしてみました。
ユークリッドの互除法 とは
二つの整数の大きい数値から小さい数値を引き続け、両者が等しくなるまで繰り返す。
等しくなった値が最大公約数。
GCMは、Greatest Common Measure（最大公約数）の頭文字が由来になっている。
コード
今回は、二つの整数から最大公約数を求めます。
言語はJavaです。
main関数内の変数 a と b に好きな数値を当てはめてください。
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;
}
}
結果は一つ目のコードと同じです。
今日の一言
アルゴリズム、わからん。