ALDS1_1_B: Greatest Common Divisor

今日は前回に続き、ALDS1_1_Bの問題を解いていきたいと思います。 問題のリンクを以下に貼っておきます。

最大公約数 | アルゴリズムとデータ構造 | Aizu Online Judge

前回はソートアルゴリズムでした。ソートアルゴリズムは重要なのでしっかり理解しましょう。 今回は最大公約数を求める問題であり、数学的な思考が要求されます。 実装は以下のようになります。

このプログラムの中で return y ? gcd(y, x % y) : x; の部分はいくらか複雑かもしれません。 これは以下のプログラムを再帰関数により再現したものと考えてもらえれば理解しやすいと思います。

このアルゴリスム(計算方法)はユーグリッド互除法と呼ばれるものです。 ユーグリッド互除法に関する数学的証明は省略させていただきます。 気になる方は検索してみてください。 自分で考えて見るのも良い勉強になると思います。