#Pythonで学ぶアルゴリズム< ユークリッドの互除法 >
##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第30弾としてユークリッドの互除法を扱う．
##ユークリッドの互除法
2つの自然数の最大公約数を求める方法として有名．
なお，最大公約数を扱う際によくgcdの文字を見かけるが，これは最大公約数を英語にしたGreatest Common Divisorの頭文字であり，最大公約数を表している．
####定理
2つの自然数a, bについて，aをbで割ったときの商をq，あまりをrとすると，「aとbの最大公約数」は「bとrの最大公約数」に等しい．
これは高校数学で学んだものである．簡単に最大公約数を求める手順について以下に示す．
【step1】: aをbで割り，あまりrを求める
【step2】: a, bをb, rでそれぞれ置き換える
【step3】: あまりrが0なら，その時の割る数bが最大公約数で，そうでなければstep1へ戻る
##実装
先ほどの説明に従って，Pythonでの実装を行う．なお，ソースコードは3つ作成した．以下にそれらのソースコードとその時の出力を示す．
#####ソースコード①（ユークリッドの互除法：自然数対応）
先ほどの手順を忠実に再現したものとなり，理解しやすいプログラム．
"""
2021/02/04
@Yuya Shimizu
最大公約数を求める（ユークリッドの互除法）
gcd : Greatest Common Divisor
"""
def gcd(a, b):
r = a % b
while r != 0:
a, b = b, r
r = a % b
return b
if __name__ == '__main__':
num1 = 120
num2 = 28
GCD = gcd(num1, num2)
print(f"({num1}, {num2}) → gcd: {GCD}")
#####出力
(120, 28) → gcd: 4
#####ソースコード①（ユークリッドの互除法：0も許容）
ソースコード①とほとんど同じだが，引数に0を入れてもエラーにならないようになっている．
"""
2021/02/04
@Yuya Shimizu
最大公約数を求める（ユークリッドの互除法）
gcd : Greatest Common Divisor
"""
def gcd(a, b):
"""変数を用意せず，直接余りを扱うことで，引数bが0でもエラーが出ない"""
while b != 0:
a, b = b, a%b
return a
if __name__ == '__main__':
num1 = 120
num2 = 28
GCD = gcd(num1, num2)
print(f"({num1}, {num2}) → gcd: {GCD}")
#####出力
(120, 28) → gcd: 4
#####ソースコード③
最後に示すプログラムは，ユークリッドの互除法を用いない方法である．これは私が他の教材で勉強した「差を用いた方法」である．（参考文献にその教材も示しておく）
簡単に説明すると，「負にならないように2つの数字を引き算していき，引く値が互いに同じとなるとき，すなわち差が0となるとき，その値が最大公約数である」というものである．このようなアルゴリズムも学んでいるので，ついでに示しておくこととする．ちなみに，除算の操作がないため，ソースコード②同様，引数に0が入力されても特に問題はない．
"""
2021/02/04
@Yuya Shimizu
最大公約数を求める（減算の利用）
gcd : Greatest Common Divisor
"""
def gcd(a, b):
while a != b:
if a > b:
a, b = b, a-b
else:
a, b = b, b-a
return a
if __name__ == '__main__':
num1 = 120
num2 = 28
GCD = gcd(num1, num2)
print(f"({num1}, {num2}) → gcd: {GCD}")
#####出力
(120, 28) → gcd: 4
##感想
今回は高校数学でも習っていたこともあり，非常に簡単であった．これで今までこれらのアルゴリズムを学んできた教材(参考文献)も学習の部分は完了した．残るは，演習の中で紹介されている．圧縮アルゴリズムだけとなった．よって，この教材を使ったアルゴリズムの学習は次回が最終回である．随分と学んだ気がするが，すべてを学んだわけではないので，また新たに学習は進める予定である．
##参考文献
Pythonで始めるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
増井 敏克 著 翔泳社
Javaによるはじめてのアルゴリズム入門 河西 朝雄 著 技術評論社