![見出し画像](https://assets.st-note.com/production/uploads/images/98326477/rectangle_large_type_2_e62720e8112e277638d206f1d5b58c81.jpeg?width=800)
'最大公約数'と'ユークリッドの互除法'には突っ込みどころがぁ・・・独学コンピューターサイエンティスト 第1部 第6章
'最大公約数'と'ユークリッドの互除法'には突っ込みどころがぁ・・・独学コンピューターサイエンティスト 第1部 第6章
独学コンピューターサイエンティスト 第1部 第6章 '最大公約数' p128 には、
その際、2つのどちらかよりも大きな数で割ろうとすると、整数になりません。そのため、2つの数の小さい方よりも大きな数でテストする必要はありません。
とあります。そしてサンプルプログラムでは、1 から'2つの数の小さい方の数'までをカウントアップさせながら全てループさせてます。しかし、'2つの数の小さい方の数'から 1 までをカウントダウンさせながらループさせれば、最初に見つかった公約数が最大公約数になり、そこでループ抜けられます。このアルゴリズムに変えれば大きく効率アップできます。
以下が p131 の2つ目のサンプルプログラムと、それをこのアルゴリズムに変更したサンプルプログラムです。
オリジナル
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))
次に、独学コンピューターサイエンティスト 第1部 第6章 'ユークリッドの互除法' 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 と y を入れ替えます。
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