アルゴリズムの例：ユークリッドの互除法
「学問に王道なし」
「楽に勉強する方法はないかなあ」と考えている人には耳の痛い格言「学問に王道なし」は、古代ギリシャの数学者ユークリッドが残した言葉とされています。元々は「幾何学に王道なし」という言葉だったそうです。
ユークリッドの名は、「ユークリッド空間」「非ユークリッド幾何学」などといった数学や物理学の言葉にも残っています。紀元前の時代に生きた人の名前が、現代の科学の世界に残っているというのは、なかなかすごいことですね。
最大公約数を求めるアルゴリズムにも、その名が冠されたものがあります。それが「ユークリッドの互除法」です。
ユークリッドの互除法
ユークリッドの互除法は、２つの数字の最大公約数を見つけるためのシンプルな方法です。
- まず、最大公約数を求めたい２つの数字を選びます。仮にa、bとします。
- ２つの値のうち、大きい方を小さい方で割り、その余りを求めます。いったん、大きい方をa、小さい方をbとし、a割るbの余りを、 r としましょう。
- 次に、余りrの値を、大きい方（ここではa）に入れます。
- 大きい方を小さい方で割った余りが０になるまで、手順2と手順3を繰り返します。
- どちらかが0になったとき、０になっていない方に残っている数が、最初に選んだ２つの数字の最大公約数です。
4桁、5桁を上回るような大きな数字どうしでも、このステップをたどれば、簡単に最大公約数を求めることが可能です。
ユークリッドの互除法で、入力された二つの整数の最大公約数を求めるプログラム
ユークリッドの互除法を使って、二つの整数の最大公約数を求めるプログラムを作ってみました。
以下のボタンをクリックすると、Monaca Educationのアカウントにプロジェクトをインポートできます。
Monaca Educationにインポートする(要ログイン)
プログラムの中では、HTMLのタグinputを使って入力を受け付け、文字列を数値に変換しています。その後、0（ゼロ）が入力されていないかチェックした上で、関数gcd()に２つの値を引き渡し、最大公約数を得ています。なお、関数の名前gcdは、最大公約数を表す英語Greatest Common Divisorの頭字語です。
ここでは、関数gcdの、ユークリッドの互除法を実行している部分に注目してみます。
なお、関数gcdには、最大公約数を求めたい２つの整数が、引数a、bとして渡されています。
また、関数gcdには、以下の処理の後ろに、計算の途中の状態（※配列stepsに記録しています）を、計算結果が出た後で画面に表示する処理が含まれています。
// 変数aが0でなく、変数bが0でない間、
// つまり変数a,bの両方が0でない間、繰り返す
while (a !== 0 && b !== 0) {
steps.push(`a: ${a}, b: ${b}`); // 計算中の値を記録
// 変数aと変数bの大小を比較して、
// 大きい方を小さい方で割った余りを求める。
// 求めた余りを、大きい方が入っていた変数に代入する
if ( a > b ) {
let r = a % b;
a = r;
} else {
let r = b % a;
b = r;
}
}
キーワードwhileを使って、繰り返し構造を作っています。引数として渡された２つの変数a、bについて、両方が０でない間、繰り返すようにしています。これで、上の文章での説明の「大きい方を小さい方で割った余りが０になるまで」を実現できます。
キーワードifを使って作っている条件分岐構造では、変数aとbの値の大小を比べています。そうして分かった「大きい方」を、「小さい方」で割り、余りを求めます。求めた余りは、変数rに代入します。そして、変数rの値を「大きい方」の変数に代入して、上書きしています。
なお、余りを求めること、その余りを「大きい方」に代入することを分けて見やすくするために、上のような書き方をしていますが、それぞれ、「a = a % b;」「b = b % a;」と書いても、結果は同じです。
これでwhileによる繰り返し構造の中の処理は終わりなので、繰り返し構造の最初に戻って、aかbのどちらかが0（ゼロ）になっていないか調べます。どちらかが0になっていたら繰り返しを終了します。
0でない方が、最大公約数です。
最大公約数を求めるアルゴリズムは、１つだけ？
この記事では、ユークリッドの互除法のアルゴリズムを使って、最大公約数を求めるプログラムを紹介しました。
最大公約数を求めるアルゴリズムは、ユークリッドの互除法だけではありません。１つの問題（例：「２つの整数について、最大公約数を求める」）には、様々なアルゴリズムがあり得ます。
アルゴリズムにも王道は無い、と言ってよいかもしれません。
