Edited at

ユークリッドの互除法 実装

AOJ ALDS1_1_Bで最大公約数を求める問題が出た。

最大公約数を求める有名なアルゴリズムとしてユークリッドの互除法というものがある。


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

非負整数a,bについて、その最大公約数をgcd(a,b)とする。

a ≥ bであるとき、gcd(a,b) = gcd(b,a%b)である。

(a%babで割った時の剰余)

これを用いて、次のようにして最大公約数を求めることができる。

1. a%bを計算する。

2. a%b0ならばbを最大公約数として出力して終了する。

3. abを代入し、ba%bを代入したうえで、1 に戻る。


実装

これを関数unsigned euclidean_gcd(unsigned a,unsigned b)として実装した。

ただし、abはともに0ではないものとする。

引数はどちらが大きくても問題ないように実装する。


最初に書いた実装

unsigned euclidean_gcd(unsigned a, unsigned b) {

while(1) {
if(a < b) swap(a, b);
if(!b) break;
a %= b;
}
return a;
}

2つの変数x,yを交換する操作をswap(x,y)とした。

求めたいものは求まるのだが、アルゴリズムがはっきり見えないし、無限ループがあらわになっていて好きになれない。


より好みな実装

unsigned euclidean_gcd(unsigned a, unsigned b) {

if(a < b) return euclidean_gcd(b, a);
unsigned r;
while ((r=a%b)) {
a = b;
b = r;
}
return b;
}

アルゴリズム通りで、あらわな無限ループもない。

追記(2018/7/23) まともに動かないコードを乗せていたことに今更気づいたので修正。ついでにswapを使わないようにした。