'最大公約数'と'ユークリッドの互除法'には突っ込みどころがぁ・・・独学コンピューターサイエンティスト 第１部 第６章

'最大公約数'と'ユークリッドの互除法'には突っ込みどころがぁ・・・独学コンピューターサイエンティスト 第１部 第６章

独学コンピューターサイエンティスト 第１部 第６章 '最大公約数' p128 には、

その際、２つのどちらかよりも大きな数で割ろうとすると、整数になりません。そのため、２つの数の小さい方よりも大きな数でテストする必要はありません。

とあります。そしてサンプルプログラムでは、1 から'２つの数の小さい方の数'までをカウントアップさせながら全てループさせてます。しかし、'２つの数の小さい方の数'から 1 までをカウントダウンさせながらループさせれば、最初に見つかった公約数が最大公約数になり、そこでループ抜けられます。このアルゴリズムに変えれば大きく効率アップできます。

以下が p131 の２つ目のサンプルプログラムと、それをこのアルゴリズムに変更したサンプルプログラムです。

オリジナル

def gcf(i1, i2):
    if i1 < 0 or i2 < 0:
        raise ValueError("テストできる数は正の整数だけです。")
    if i1 == 0:
        return i2
    if i2 == 0:
        return i1

    if i1 > i2:
        smaller = i2
    else:
        smaller = i1

    for divisor in range(1, smaller+1):
        if (i1 % divisor == 0) and (i2 % divisor == 0):
            gcf_value = divisor

    return gcf_value

print(gcf(-2, 22))

改良版

def gcf(i1, i2):
    if i1 < 0 or i2 < 0:
        raise ValueError("テストできる数は正の整数だけです。")
    if i1 == 0:
        return i2
    if i2 == 0:
        return i1

    if i1 > i2:
        smaller = i2
    else:
        smaller = i1

    # 以下を改造！
    for divisor in range(smaller, 0, -1):
        if (i1 % divisor == 0) and (i2 % divisor == 0):
            return divisor

print(gcf(20, 12))

次に、独学コンピューターサイエンティスト 第１部 第６章 'ユークリッドの互除法' p133 サンプルプログラムには無駄な部分があります。

以下がそのサンプルプログラムです。

def gcf(x, y):
    if y == 0:
        (x, y) = (y, x)
    while y != 0:
        (x, y) = (y, x % y)
    return x
    
print(gcf(20, 12))

'ユークリッドの互除法' p133 には、

コードの最初の行で境界条件における処理を書きます。y が 0 のとき、割り算では 0 で割れないので、Python が例外処理を行います。これを避けるために、y が 0 のときには x と ｙ を入れ替えます。

if y == 0:
    (x, y) = (y, x)

とあります。しかし、まずこの処理では、x も 0 の場合、入れ替えても y は 0 のままなので無意味です。そしてそれ以前に x を y で割る処理がある while ループの条件式が y != 0 なので、y が 0 の場合は一度もループせず、決して 0 割りが起きることはありません。この境界条件における処理は完全に無意味です。この処理を取り除いたサンプルプログラムを以下に示します。

def gcf(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x
    
print(gcf(20, 12))

後書き

'ユークリッドの互除法' p133 サンプルプログラムを見たときは、正直なんだかなぁ (´-﹏-`；)💦 でした。。。

#最大公約数
#ユークリッドの互除法
#日経BP
#日経BP_ITブックス
#独学コンピューターサイエンティスト
#独CS #selftaughtcoder
#清水川貴之 さん
#CoryAlthoff さん
#Python #Python3