#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つ作成した．以下にそれらのソースコードとその時の出力を示す．

ソースコード①（ユークリッドの互除法：自然数対応）

先ほどの手順を忠実に再現したものとなり，理解しやすいプログラム．

gcd1.py

"""
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を入れてもエラーにならないようになっている．

gcd2.py

"""
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が入力されても特に問題はない．

gcd3.py

"""
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によるはじめてのアルゴリズム入門　　河西朝雄　著　技術評論社