2013-03-12

「アルゴリズムを、はじめよう」ユークリッドの互除法をPythonで書く

2つの数字の最大公約数を導きだすユークリッドの互除法のアルゴリズムをPythonで書きました。

アルゴリズムを、はじめよう

第12章:ユークリッドの互除法のアルゴリズム(Euclidean algorithm)


#!/usr/bin/env python
#!/usr/bin/env python
#-*- coding: utf-8 -*-

def euclidean():
    a = int(raw_input("Enter the first number. : "))
    b = int(raw_input("Enter the second number. : "))
    ans = 1
    if a < b:
        a, b = b, a
    while 1:
        r = a % b
        if r == 0:
            ans = b
            break
        else:
            a = b
            b = r
    print "The greatest common divisor is %d." % ans

if __name__ == '__main__':
    euclidean()

これはけっこう簡単にできた。フローチャートを見てもけっこう単純。こんな簡単に最大公約数が出せるなんて知らなかった。

0 件のコメント:

コメントを投稿