Eukleides（ユークリッド）のアルゴリズム
スポンサーリンク
Elements(原論)の中の解法を用いて既約分数（これ以上割れない分数）を計算する。
難しく書いたが要するに
最大公約数は何か？と言う回答を吐き出すプログラムを作れればよい。
解答に至る手順として最大公約数（Greatest Common Divisor。以下gcd）を求めればそれを分子、分母共に割ってやればおのずと既約分数が出てくる。
さて、最大公約数を求める能率的な方法として古代ギリシャ人の解法を用いる。
これは「分母と分子を比べ分母が大きいなら分母と分子の最大公約数が分子と分母-分子の最大公約数に等しい。」ということに基づく。
混乱しないように例を挙げると、200/300という分数の最大公約数は200と100の最大公約数と等しいということだ。ただ、世の中こんなに単純な最大公約数ばかりではない。
そこから考えて、分母ー分子で出てきた答えを使えないだろうか？
さらに分子で引くと同様に「（分母ー分子）と分子ー（分母ー分子）の最大公約数」が「分子と分母-分子の最大公約数」に等しいのは分かる。
即ちこれを繰り返していけばいずれ引く値が同じになるところまで来る。
例として85/136は分母ー分子＝51。85-51=34。51-34=17。34-17=17。17-17=0//
見やすくする為、一般化した式で書けば
- 分母をuと置き分子をｖと置く。
- vとu-v ｛但しu>v｝のgcdはuとvのgcdに等しい。
- u-vとv-(u-v)｛但しv>(u-v)｝のgcdはvとu-v｛但しu>v｝のgcdに等しい。
- この動作を繰り返していき引く数と引かれる数が等しくなったときその数がuとvのgcdとなる。
ただ、これは常に引かれる数のほうが小さいと言う前提がある。
引かれる数の方が引く数より大きくなってしまった場合、
仮に41/161など161-41=120など。v<(u-v)となってしまったらプログラム内でその２つをひっくり返す動作（スワップ処理）をしなければならない。
一番簡単な処理として
- temp=a;
- a=b;
- b=temp;
と言うaとbの入れ替え動作があるので知っておくと便利。
では同様に6536/7144は分母ー分子＝608。6536-608=5928。5928-608=5320。5320-608=4712。4712-608=4104。4104-608=3496。3496-608=2888。2888-608=2280。2280-608=1672。1672-608=1064。1064-608=456。608-456=152。456-152=304。304-152=152 152-152=0//
合っていてよかった。2888や456なんかが出てきてくれて嬉しい。ともかくこんな感じである。gcdは152。
プログラム例は
#include<stdio.h>
int gcd(int u,int v)
{
int t;
while (u>0)
{
if(u<v)
{t=u;u=v;v=t;} /*swap処理*/
u=u-v;
}
return v;
}
main()
{
int x,y;
while(scanf("%d %d",&x,&y)!=EOF)
{
if(x>0&&y>0)
printf("x=%d y=%d gcd=%d\n",x,y,gcd(x,y));
}
}
結果
6 4
x=6 y=4 gcd=2
200 300
x=200 y=300 gcd=100
6536 7144
x=6536 y=7144 gcd=152といった感じである。
