ActionScript入門Wiki - ユークリッドの互除法

トップページ > アルゴリズム > ユークリッドの互除法

概要

最大公約数を求めることが出来るユークリッドの互除法というアルゴリズムを利用してみましょう。

アルゴリズム

例として48と21の最大公約数を求める場合、

48 / 21 = 2...6

のように二つの値を割って余りを求めます。

21 / 6 = 3...3
6 / 3 = 2...0
3 / 0

それ以降は、割る数が0になるまで割る数と余りを割っていきます。

割る数が0になったときの割られる数が最大公約数になるので、48と21の最大公約数は3ということになります。

証明

a, bが自然数で、aはb以上の値だとします。
aとbの最大公約数をgcd(a, b)、
aをbで割った時の商をq、余りをrだとして、

gcd(a, b) = gcd(b, r)

が成り立つということをまず証明します。

aをbで割った時の商をq、余りはrを式にすると

a = bq + r

になります。

gcd(a, b) = d

だとすると、dはaとbの公約数です。

a,bとdの関係は、

a = a' * d
b = b' * d

と表せます(dはaとbの約数なので、dにa'を掛けたものがa、dにb'を掛けたものがbになる)

a = bq + r

の、aをa' * d、bをb' * dに置き換えると、

a' * d = b' * d * q + r

になります。

a' * dはdをa'個足しあわせたもの、
b' * d * qはdをa' * q個足しあわせたものと考えることが出来るので、式の後ろで足し合わされているrはdで割り切れます。
つまり、dはbとrの公約数であることが分かります。

aとbの公約数の集合(全ての公約数)と、bとrの公約数の集合は等しいので、集合の中で最大となる公約数同士も等しいということになります。

gcd(a, b) = gcd(b, r)

になるということが分かったので、実際に具体的な値を入れてみましょう。

gcd(48, 21) = gcd(21, 6) = gcd(6, 3) = gcd(3, 0) = 3

になります。

プログラム

非再帰

trace(gcd(48, 21)); // 3
trace(gcd(21, 48)); // 3
 
private function gcd(a:int, b:int):int
{
	while (b > 0)
	{
		var r:int = a % b;
		a = b;
		b = r;
	}
 
	return a;
}

再帰

trace(gcd(48, 21)); // 3
trace(gcd(21, 48)); // 3
 
private function gcd(a:int, b:int):int
{
	if (b == 0) return a;
	else return gcd(b, a % b);
}

ユークリッドの互除法はa >= bであるということが前提条件です。
ただAS3の場合、a < bのときにa % b = aが返ってくるので、

b = a % b
a = b

と一回目の関数内で値が反転するので、特に交換処理を記述する必要はありません。(ループは一回増えますが)

検証用コード

package
{
	import flash.display.Sprite;
 
	public class Main extends Sprite
	{
		public function Main()
		{
			trace(gcd(48, 21));
			trace(gcd(21, 48));
		}
 
		private function gcd(a:int, b:int):int
		{
			while (b > 0)
			{
				var r:int = a % b;
				a = b;
				b = r;
			}
 
			return a;
		}
	}
}

リンク元(0)