C++ と Ruby で、ユークリッドの互除法を使って2つの自然数の最大公約数を求めるプログラムを作成してみました。
まず、ユークリッドの互除法について、
「自然数 a, b ( a > b ) について、a を b で割った剰余を r とすると、a と b の最大公約数は b と r の GCD に等しい。」
という性質が成り立つ。
この性質を利用して、b を r で割った剰余、除数 r をその剰余で割った剰余、と逐次計算を繰り返すと、いずれ剰余が 0 になる。
そして、その時の除数が a と b との最大公約数となる。
また、自然数 a と b ( a > b )の最大公約数を求めることは、a - b と b の最大公約数を求めることに置き換えることもできる。
※ユークリッドの互除法の詳細については、中学生(小学生?)レベルのお話なのでここでは詳細な説明は省かせていただくことにする。
アルゴリズムとしてまとめると、以下のようになります。
- a ≠ b の間、以下を繰り返す。
- a > b なら、 a = a - b
- 上記以外なら、b = b - a
- a(=b) が求める最大公約数となる。
※a と b の差が大きい場合は、上記(1) の a = a - b, b = b - a を a = a % b, b = b % a と置き換えると効率がよい。
ちなみに、プログラミングの知識のない方のために一言言っておくと、"=“ は代入の意味で使用します。
0. 前提条件
- Cygwin 1.7.15
- g++ (GCC) 4.7.1
- Ruby 1.9.3-p194
- 再帰的に計算する関数を作成しました。
- 入力チェック等詳細なエラー処理は非搭載。
- 大きすぎる数(int 型の範囲を超えた数等)を入力すると、正しい結果は得られません。
1. C++ ソース作成
今回作成した C++ ソースは以下の通りです。 C++ なのでオブジェクト指向な作りにしています。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
|
2. C++ ソースコンパイル
以下のコマンドで C++ ソースをコンパイルする。
1
|
|
何も出力されなければ成功です。
3. 実行
実際に実行して最大公約数を計算する。
1 2 3 4 5 |
|
4. Ruby スクリプト作成
今回作成した Ruby スクリプトは以下の通り。(オブジェクト指向な作りにしている)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
5. Ruby スクリプト実行
まず、実行権限を付与。
1
|
|
そして、実行。
1 2 3 4 5 |
|
今回はちょっと簡単すぎました。
しかし、様々なアルゴリズムを考えてみる事によって、同じアルゴリズムでも言語によってどう異なってくるのか等を把握できるようになると思います。
以上。