mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

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

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

こんばんは。

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++ なのでオブジェクト指向な作りにしています。 【 ファイル名: 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 << "1つ目の自然数:";
        scanf("%d", &a);
        cout << "2つ目の自然数:";
        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++ Euclid.cpp -o Euclid

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

3. 実行

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

1
2
3
4
5
$ ./Euclid
1つ目の自然数:128
2つ目の自然数:72
a = 128, b = 72
最大公約数 = 8

4. Ruby スクリプト作成

今回作成した Ruby スクリプトは以下の通りです。 オブジェクト指向な作りにしています。 【 ファイル名: euclid.rb 】

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
# -*- coding: utf-8 -*-
class Euclid
  # 計算クラス
  class Calc
    # 最大公約数計算
    def calc_gcd(a,  b)
      return b == 0 ? a : calc_gcd(b, a % b);
    end
  end

  # メイン処理
  begin
    # データ入力
    print "1つ目の自然数:"
    a = gets.chomp.to_i
    print "2つ目の自然数:"
    b = gets.chomp.to_i
    puts "a = #{a}, b = #{b}"

    # 最大公約数計算
    obj_calc =Calc.new
    puts "最大公約数 = #{obj_calc.calc_gcd(a, b)}"
  rescue => e
    # エラーメッセージ
    puts "例外発生!"
  end
end

5. Ruby スクリプト実行

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

1
2
3
4
5
$ ruby euclid.rb
1つ目の自然数:128
2つ目の自然数:72
a = 128, b = 72
最大公約数 = 8

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

以上。

Comments