再帰的プログラミングで最大公約数を求める（ユークリッドの互除法）

気合入れてブログをはじめてみましたが、研究が忙しく、ブログの更新を後回しにしてしまいがちです。

毎日、更新していている方々を心から尊敬します。

では、さっそく本題に入ります。 今日は再帰的プログラミングで最大公約数を求めるアルゴリズムを実装します。

最大公約数とは

　2つ以上の正の整数の公約数のうち、最大値となるものをいいます。

　公約数についてはこちらを参考にしてください

　公約数の求め方｜もう一度やり直しの算数・数学

　例えば、18と6の最大公約数は、”6”になります。 　

　解答

　まず、二つの正の整数を約数に分解します。

　18 = 3 * 3 * 2,　6 = 3 * 2 * 1

　18 = 3 * 6,         6 = 6 * 1

　上の約数をなるべく大きくかつ二つの整数に共通して存在するように乗算すると6になります。

　手計算で最大公約数を求める場合、約数に分解して考えることが一般的ですよね。

　でも実は、そんなことをしなくても確実に求めることができるアルゴリズム（手法）が存在します。

　その名も

　　ユークリッドの互除法

　です。

　とても名前の響きがいい、かっこいいです。

　このブログを理解した中学生の皆さんは、是非数学の先生にこのアルゴリズムについて尋ねてみてください。

　雑談はさておき。。。 　

　では、どういうアルゴリズムなのか実際に日本語で理解しましょう。 　

　二つの整数をx、yとし考えます。

　　1．xをyで割り、余りを求めます。

　　2．余りが0なら最大公約数はyです。

　　3．余りが0でなければ、xにy、

　　　 yに余りを代入し、1.に戻ります。

　やってることが割り算だけなのでとても単純ですね。

　実際に、32と24で考えてみましょう。

　　1．32÷24の余りは、8

　　2．余りが0でないので、32のところに24、

　　　 24のところに8を入れる。

　　3．24÷8の余りは0。よって最大公約数は8。

　数字で見るとよりわかりやすいです。他の数字でも試してみてください。

　では、実装に入りましょう。言語はPythonです。

import sys

def main():

    #int()でinput()の入力値を整数型にします。
    x = int(input("一つ目の整数を入力してください"))
    y = int(input("二つ目の整数を入力してください"))

    #アルゴリズム1. 2. 3. を繰り返す関数に二つの整数を格納し、結果を取得
    ans = euclidean(x, y)

    ##結果の呼び出し
    print("%dと%dの最大公約数は%dです" % (x, y, ans))



def euclidean(x, y): 

    #x÷yの余りを計算しrに格納
    r = x % y

    #余りが0の場合yが最大公約数
    if (r == 0):

        return y

    #余りが0以外のときは、xにy、yに余りを代入、もう一度余りを計算
    #ある関数が自分自身を呼ぶことを再帰と言う。
    else :

        return euclidean(y, r)

if __name__ == "__main__":
    main()

結果は次の通りです。

一つ目の整数を入力してください132

二つ目の整数を入力してください24

132と24の最大公約数は12です

関数が自分自身を呼ぶことを再帰的プログラミングといいます。

これを使うことで、同じことをある条件まで繰り返すようなプログラムをコンパクトに書くことができます。

今日はここで。

bye！！！