ユークリッドの互除法完成！！！
アルゴリズムの定番であるユークリッドの互除法のプログラムが完成しました。所要時間は前回の記事を書いてから始めて11時くらいにできたので、およそ1時間半くらいです。まったくてこずらせやがって、ユークリッドさん。
ちなみにユークリッドの互除法というのは、2つの数の最大公約数を求めるアルゴリズムで、
（コンピュータプログラムでは）次のように行います。
1．2つの数A,Bをとる
2．AをBで割り、Cを記憶する。
3．余りCが0------------>Bが最大公約数。
4．余りCが0でない------>AをBで置き換え、BをCで置き換える。----->2．に戻る。
たとえば、1395と2784の場合
2784÷1395 余り1389
1395÷1389 余り6
1389÷6 余り3
6÷3 余り0
3が最大公約数。
詳しくはユークリッドの互除法 - Wikipediaを参照。
ではそのコード
import java.io.*; public class Euclid { public static void main(String[] args) throws IOException { System.out.println("2つの数を入力してください。"); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str1 = br.readLine(); String str2 = br.readLine(); int eu1 = Integer.parseInt(str1); int eu2 = Integer.parseInt(str2); int amari = eu1%eu2; //※1 if(eu1<eu2){ int tmp = eu1; eu1 = eu2; eu2 = tmp; amari = eu1%eu2; } System.out.println(""); System.out.println(eu1+"と"+eu2+"との最大公約数を求めます。"); for(int i=1; i<=12; i++){//※2 //※3 if(amari != 0){ eu1 = eu2; eu2 = amari; amari = eu1%eu2; } } System.out.println(""); System.out.println("最大公約数は"+eu2); ｝ }
実行結果例１
2つの数を入力してください。 12 18 18と12との最大公約数を求めます。 最大公約数は6
実行結果例2
2つの数を入力してください。 1365 3654 3654と1365との最大公約数を求めます。 最大公約数は21
※1のところで、1つ目の入力数と2つ目の入力数の間で大小関係なく、ちゃんとプログラムが動くようにしています。これを書かないと、小さい数を大きい数で割るということになる可能性があり、その場合ユークリッドの互除法とは異なった値を返してしまうからです。
※2のところで、
for(int i=1; i<=12; i++)
としていますが、i<=12という部分の12という数字はちょっと問題があったりします。この部分によってユークリッドの互除法のアルゴリズムを12回行うのですが、これは経験的にほとんどの場合、12回以内にアルゴリズムの手続きが終了して最大公約数が分かるということを期待して書いているのであって、最大公約数を見つけたからアルゴリズムを終了しているわけではないのです（もっともっと大きい数の最大公約数を求めたいなら12じゃなくて100や10000にする)。普通に最大公約数を出力するだけなら問題はないのですが、※3のような時にはちょっと美しくない。
※3のところに
System.out.println(eu1+"÷"+eu2+" 余り"+amari);
を入れるとユークリッドの互除法の途中計算が出力されます。たとえば、
2つの数を入力してください。 1365 3654 3654と1365との最大公約数を求めます。 3654÷1365 余り924 1365÷924 余り441 924÷441 余り42 441÷42 余り21 42÷21 余り0 42÷21 余り0 42÷21 余り0 42÷21 余り0 42÷21 余り0 42÷21 余り0 42÷21 余り0 最大公約数は21
と出力されます。途中まではいいのに・・・。12回出力するプログラムだから12回以内に最大公約数を 見つけてもそこでストップしないのです。う〜むむ、どうすればよいのだろ。 まだまだ未熟者が書いたプログラムですから、変なところ、もっとうまくできるところ、 あふぉなところがいろいろとあると思います。もし気付いた方がいたらご教授ください(´・ω・`)
