C++, Ruby - ユークリッドの互除法！

[ プログラミング, 数学 ] [ C言語, Ruby ]

C++ と Ruby で、ユークリッドの互除法を使って２つの自然数の最大公約数を求めるプログラムを作成してみました。

まず、ユークリッドの互除法について、
「自然数 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++ なのでオブジェクト指向な作りにしています。

gcd_euclid.cpp
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

/*********************************************
 * ユークリッドの互除法（再帰的に求める方法） 
 *********************************************/
#include <iostream>
#include <stdio.h>

using namespace std;

/*
 * 計算クラス
 */
class Calc
{
    public:
        // 最大公約数計算
        int calcGCD(int a, int b);
};

/*
 * 最大公約数計算
 */
int Calc::calcGCD(int a, int b)
{
    if (b == 0) {
        return a;
    } else {
        return calcGCD(b, a % b);
    }
}

/*
 * メイン処理
 */
int main()
{
    int a, b;

    try {
        // データ入力
        cout << "１つ目の自然数：";
        scanf("%d", &a);
        cout << "２つ目の自然数：";
        scanf("%d", &b);
        cout << "a = " << a << ", "
             << "b = " << b << endl;

        // 計算
        Calc objCalc;
        cout << "最大公約数 = " << objCalc.calcGCD(a, b) << endl;
    }
    catch (...) {
        cout << "例外発生！" << endl;
        return 1;
    }
    return 0;
}

2. C++ ソースコンパイル

以下のコマンドで C++ ソースをコンパイルする。

1

$ g++ gcd_euclid.cpp -o gcd_euclid

何も出力されなければ成功です。

3. 実行

実際に実行して最大公約数を計算する。

1
2
3
4
5

$ ./gcd_euclid
１つ目の自然数：128
２つ目の自然数：72
a = 128, b = 72
最大公約数 = 8

4. Ruby スクリプト作成

今回作成した Ruby スクリプトは以下の通り。（オブジェクト指向な作りにしている）

gcd_euclid.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#! /usr/local/bin/ruby
# ********************************************
#  ユークリッドの互除法（再帰的に求める方法） 
# ********************************************

class Calc
  def calc_gcd(a,  b)
    return b == 0 ? a : calc_gcd(b, a % b);
  end
end

begin
  print "１つ目の自然数："
  a = gets.chomp.to_i
  print "２つ目の自然数："
  b = gets.chomp.to_i
  puts "a = #{a}, b = #{b}"
  obj_calc = Calc.new
  puts "最大公約数 = #{obj_calc.calc_gcd(a, b)}"
rescue => e
  $stderr.puts "例外発生！"
end

5. Ruby スクリプト実行

まず、実行権限を付与。

1

$ chmod +x gcd_euclid.rb

そして、実行。

1
2
3
4
5

$ ./gcd_euclid.rb
１つ目の自然数：128
２つ目の自然数：72
a = 128, b = 72
最大公約数 = 8

今回はちょっと簡単すぎました。

しかし、様々なアルゴリズムを考えてみる事によって、同じアルゴリズムでも言語によってどう異なってくるのか等を把握できるようになると思います。

以上。