最大公約数を求めるプログラム

アルゴリズム

最大公約数とは

幼稚園生
幼稚園生

最大公約数って何?

先生
先生

そんなこともわからないの?仕方ないですね。wikipediaで調べてみましょう。

最大公約数(さいだいこうやくすう、: greatest common divisor[注釈 1])とは、すべての公約数約数にもつ公約数である。特に正の整数では、最大公約数は通常の大小関係についての最大の公約数と一致し、その存在性はユークリッドの互除法により保証される。

wikipedia
幼稚園生
幼稚園生

うー、わからない。

先生
先生

例えば、2016という数字が与えられた時、20は{1, 2, 4, 5, 10, 20}で割り切れる。

また、16は{1, 2, 4, 8, 16}で割り切れます。この数を、約数と言います。

2016のそれぞれの約数で被っているのは{1, 2, 4}だね。これを公約数というんだ。

最大公約数とは、公約数のうち最大の数値のことを言うんだ。つまり、2016の最大公約数は{4}ですね。

幼稚園生
幼稚園生

わかったぁ。

簡単だね。アルゴリズムが浮かんできたよ!!

ユークリッド互除法ってのはなんだかわかんないけど....

先生
先生

お!じゃ早速、思いついたアルゴリズムで求めてみよっか.

ユークリッド互除法は、その後に教えよう。

幼稚園生のアルゴリズム

幼稚園生
幼稚園生

じゃ、C++を用いて書くよ。

幼稚園生
幼稚園生

まずは、標準入力で2つの数値を取得するんだ

cin >> a >> c;
幼稚園生
幼稚園生

取得した2つの数値の内、小さい方の数値をコピーしてその値をGとして、2つの数値をG, G-1, G-2, ...., 1で割っていくんだ

1, 2, 3って小さい方の数値から割っていくよりも、大きい方の数値から見つける方が、最大公約数を見つけるのが速くなるって気づいたから、大きい方から割っていくよ。

if (a > c) {
  for (int i = c; i >= 1; i--) {
            // if (a % i == 0 && c % i == 0) return i;
        }
    } else if (a < c) {
        for (int i = a; i >= 1; i--) {
            // if (a % i == 0 && c % i == 0) return i;
        }
    }
幼稚園生
幼稚園生

最初に割り切れた数値が最大公約数になるよ

if (a > c) {
  for (int i = c; i >= 1; i--) {
            // if (a % i == 0 && c % i == 0) return i;
        }
    } else if (a < c) {
        for (int i = a; i >= 1; i--) {
            // if (a % i == 0 && c % i == 0) return i;
        }
    }
幼稚園生
幼稚園生

これで完成!と思いきや、引っ掛け!

取得した2つの値が同じ時、その数値自体が最大公約数になることを忘れないこと

 else {
        result = a;
    }
幼稚園生
幼稚園生

よし! これで完成!

全部のコードを見せるよ

#include <iostream>
using namespace std;
int a, c;

int mmcm() {
    int result = 0;
    if (a > c) {
        for (int i = c; i >= 1; i--) {
            if (a % i == 0 && c % i == 0) return i;
        }
    } else if (a < c) {
        for (int i = a; i >= 1; i--) {
            if (a % i == 0 && c % i == 0) return i;
        }
    } else {
        result = a;
    }
    return result;
}

int main() {
    cin >> a >> c;
    int result;
    result = mmcm();
    cout << result << endl;
    return 0;
}
幼稚園生
幼稚園生

実行だ!

// input
30 6

// output
6
幼稚園生
幼稚園生

できたーー!

先生
先生

すごいですね!あの説明だけで....

正解です。

しかし、甘いですね。

そのアルゴリズムには欠点があります。

幼稚園生
幼稚園生

欠点ってなんだよ。

先生
先生

取得した2つの数値が小さい数値なら、欠点箇所は特にありません。

しかし、大きい数値ならどうでしょうか?

例えば、1垓1京1兆1億と1011垓921京112兆14億の時、計算量が多くなることは容易に想像できませんか?

幼稚園生
幼稚園生

た、確かに!

幼稚園生
幼稚園生

もしかして、そこでユークリッド互除法ですか?

先生
先生

正解! 感の良いガキは好きだよ

ユークリッド互除法で最大公約数を求める

先生
先生

ごちゃごちゃ説明しても意味わからなくなるので、いきなりコードを見せるよ

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int x, int y) {
    int r;
    // xとyの値を比較して、以降y < x であることを保障する
    if (x < y) swap(x, y);
    while (y > 0) {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}
幼稚園生
幼稚園生

とても簡単そう!

先生
先生

そうなんだ! 意外と簡単なんだ

実際の処理はこれだけ

while (y > 0) {
        r = x % y;
        x = y;
        y = r;
    }
先生
先生

じゃ、何をやっているのかを説明するよ。

この時点で、xが大きいことが明らかであることは前提

r = x % y xyで割って、あまりをrとする

x = y xyを代入

y = r yrを代入する

yが0になるまでこれを繰り返す

先生
先生

そして、while文を抜けたときのxの値が最大公約数になるんだ

幼稚園生
幼稚園生

すごい! わかった

けどなんで、最大公約数になるの??

先生
先生

wikipediaのアニメーションがわかりやすかったから

これを見るといいよ

以上

コメント

タイトルとURLをコピーしました