AOJ ALDS1_1_Bで最大公約数を求める問題が出た。
最大公約数を求める有名なアルゴリズムとしてユークリッドの互除法というものがある。
#ユークリッドの互除法とは
非負整数a
,b
について、その最大公約数をgcd(a,b)
とする。
a ≥ b
であるとき、gcd(a,b) = gcd(b,a%b)
である。
(a%b
はa
をb
で割った時の剰余)
これを用いて、次のようにして最大公約数を求めることができる。
1. a%b
を計算する。
2. a%b
が0
ならばb
を最大公約数として出力して終了する。
3. a
にb
を代入し、b
にa%b
を代入したうえで、1 に戻る。
#実装
これを関数unsigned euclidean_gcd(unsigned a,unsigned b)
として実装した。
ただし、a
とb
はともに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
を使わないようにした。