最大公約数（除算禁止）
Posted feedbacks - Python
減算を繰り返して割り算の代わりにする方法だと差が大きいときに問題になる、ということで 「文字列の長さをみて小さい側を10**n倍する」 という荒技を使ってみました。
# Screencast-o-maticで撮りながら作ったのにアップロード中にブラウザが落ちて消滅…orz
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def gcd(x, y):
if x == y: return x
if x < y: y, x = x, y
lx = len(str(x))
ly = len(str(y))
diff = lx - ly
z = abs(y * 10 ** diff - x)
z2 = abs(y * 10 ** (diff + 1) - x)
z = min(z, z2)
if diff > 0:
z2 = abs(y * 10 ** (diff - 1) - x)
z = min(z, z2)
# zはxとyと公約数を共有する
if z < y:
return gcd(y, z)
return gcd(z, y)
|
186 #4590() Rating0/8=0.00
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
1 reply [ reply ]