【第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