AOJ ALDS1 1_B（Greatest Common Divisor）を解く

Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の1_B問題をC++で解いてみました。

ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#1「入門」は、このコースの導入となっています。

問題（1_B: Greatest Common Divisor）

問題はリンク先をご覧ください。

AOJ ALDS1 1_B問題: Greatest Common Divisor

ユークリッドの互除法について学びます。

ユークリッドの互除法について

2つの自然数から最大公約数を求める問題です。

最大公約数を求めるために、ユークリッドの互除法というアルゴリズムが使えることは高校数学（数学A）で学びます。

関数 gcd としてに実装すると以下となります。アルゴリズムの本質は6行目となります。

int gcd(int a, int b)
{
	if (b == 0) {
		return a;
	} else {
		return gcd(b, a % b);
	}
}

関数の第2引数は指数的に小さくなります。具体的な計算量は、$O(\log b)$ となります。

C++ プログラム例（ALDS1 1_B）

2つの自然数 x、y を読み込み、上記で紹介した gcd を呼び出して、結果を表示します。。

以下が、C++プログラムとなります。

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
	if (b == 0) {
		return a;
	} else {
		return gcd(b, a % b);
	}
}

int main()
{
	int x, y;
	cin >> x >> y;

	cout << gcd(x, y) << endl;

	return 0;
}

C++17からは、標準ライブラリで関数 gcd が提供されています。numeric をインクルードして、同じように関数 gcd を呼び出します。プログラムをサイトに提出する場合、言語は、「C++17」を選択してください。

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

int main()
{
	int x, y;
	cin >> x >> y;

	cout << gcd(x, y) << endl;

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

導入の第2段として、ユークリッドの互除法を使って最大公約数を求めました。再帰関数を使ったプログラムとライブラリ関数を使ったプログラムを紹介しました。

引き続き、ALDS1 の問題を紹介していきます。