14
12

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2015-07-05

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を使わないようにした。

14
12
6

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
14
12

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?