ユークリッドの互助法

ユークリッドの互助法という名前のアルゴリズムを紹介します。これは最大公約数を求めるアルゴリズムで、

ある整数x,yの最大公約数gcd(x,y)の解を求めるとして、yが0であればx、そうでなければgcd(y, x % y)が解となる。

という至って単純なアルゴリズムです。

以下のコードはこのアルゴリズムを再帰で実装したものです。ループで実装したコードはコメントアウトされています。(再帰のほうが断然エレガントである)

sample/GCDSample.java

package sample;

public class GCDSample {

	public static int gcd(int x, int y) {
		return y == 0 ? x : gcd(y, x % y);
	}

/*
	public static int gcd(int x, int y) {
		while (y != 0) {
			int t = x % y;
			x = y;
			y = t;
		}
		return x;
	}
*/
	public static void main(String[] args) {
		System.out.println(gcd(1071, 1029);
	}
}

2010年7月20日 | カテゴリー：アルゴリズム