ちょっとPython! - ユークリッドの互除法
最大公約数をもとめます。ユークリッドの互除法は以下。
1 2つの自然数aとbがあったとする（ここではa＞bとする）
2 aをbで割った余りrを求める。
3 余りrが0であれば、直前の割り算における除数（b）が最大公約数である
4 余りrが0でなければ、bをrで割って新たに余りrの値を求める
5 余りが0になるまで3と4を続ける
条件は"a > b"。参考サイトのものを少し変更しています。
def gcd(a, b):
if b == 0:
return a
m = a % b
print(a, b, m)
return gcd(b, m)
my_gcd = gcd(144, 84)
print(my_gcd)これを実行すると
144 84 60
84 60 24
60 24 12
24 12 0
12となります。
24 12 0
この場合以下のコードで経過を出力しています。
print(a, b, m)変化がわかりやすいですね。
答えとしては、余り”m"が"0"になるのは"b"が"12"なので結果は"12"となります。
if b == 0:
return a最後の出力の時は余り"m"が"b"になりその時の"b"は"a"なので答えは"a"となります。
a をbで割ってあまりがmとなるのですが、分かりにくいのが
return gcd(b, m)ですね。mは余りなんですがbの位置にあり、bはaの位置移動しています。
最初定義してあるa,bの位置が中心の関数ですが再帰する時には引数が変化するので少し注意して考えることが必要です。
再帰のみを書くとシンプルになります。
def gcd(a,b):
if b == 0:
return a
else:
return gcd(b,a % b)
test = gcd(144,84)
print(test)これで同じ結果がでます。
再帰を使わない方法では
def gcd(a, b):
while b != 0:
temp = b
b = a % b
a = temp
return aとすることもできます。これはwhileを使って連続的に判定していきます。