選挙前は公約って言葉をよく聞くけど、その後ってどうなったのか聞かないよね。
まあ、約束なんだから守られていることだろうｗ
再帰処理を使って、ユークリッドの互除法で最大公約数を求めるサンプル
ユークリッドの互除法で最大公約数を求めます。
余りがなくなるまで割り算を続けます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public class EuclideanGcdTest { public static void main(String[] args) { //ユークリッドの互除法で最大公約数を求める int answer = calcEuclideanGcd(6747, 5017); //計算結果（最大公約数）を出力 System.out.println("最大公約数は... " + answer); } public static int calcEuclideanGcd(int a, int b) { if (b == 0) { //余りがなくなったら、最大公約数 return a; } //余りがあったら再帰で続ける return calcEuclideanGcd(b, a % b); } } |
実行結果
1 | 最大公約数は... 173 |
サンプルの解説
ユークリッドの互除法は、２つの自然数の最大公約数を求めるアルゴリズムです。
余りがなくなるまで割り算を続けるために、再帰処理しています。
このアルゴリズムは、紀元前にはあったそうで。。すごいですよね。
