俺とプログラミング

某IT企業でエンジニアをしてます。このブログではプログラミングに関わることを幅広く発信します。

【第1回】Pythonで学ぶアルゴリズム講座 【ユークリッドの互除法】

これから何回かに分けて基本的なアルゴリズムについて、Pythonでの実装を踏まえて紹介していきたいと思います。

第1回目は史上最古のアルゴリズムとされるユークリッドの互除法です。
ユークリッドの互除法(Euclidean Algorithm)は主に最大公約数を求めるために使われるアルゴリズムです。情報系ならば誰もが知っています。


ユークリッドの互除法

入力および実行手順
入力 : 整数 X, Y (>0)
step 1.  XをYで割った余りをZとする。Zが0であればYを出力して終了。
step 2.  新たにXをYとし、YをZとしてstep 1.に戻る。


ユークリッドの互除法の便利な点に、XとYの大小関係はどちらでもよいということが挙げられます。本来、割った余りを求めるのですから、入力値はYよりもXのほうが大きくあるべきです。しかし、仮にYのほうが大きい場合でも、step 2.を実行することにより、XとYが入れ替わるのです。

Pythonによる実装例

# gcdは最大公約数(greatest common divisor)の意
def gcd( x, y ):
    while y != 0:
        x, y = y, x%y

print gcd( 1071, 1029 )
# 実行結果 21


初めてのPython 第3版

Copyright © 2016 ttlg All Rights Reserved.