最大公約数（除算禁止）
Posted feedbacks - Haskell
kozima さんと同じ Josef Stein のアルゴリズム． ついでに，fibも同様の2進計算で高速計算． Haskellにとっては呼び出しカウントのほうが面倒． (とりあえずナイーブにやっちゃった．) 呼出回数は1936でした． *Main> uncurry gcd' (fib 1999) 0 (1,1936)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | import Prelude hiding (gcd)
fib 0 = (0,1)
fib n | even n = let (a,b) = fib (n-1) in (b, a+b)
| odd n = let (a,b) = fib (halve (n-1)) in (b*b+a*a, b*b+2*a*b)
halve = (`div` 2)
gcd 1 _ = 1
gcd a b | a == b = a
| even a = if even b then 2*gcd (halve a) (halve b) else gcd b (halve a)
| odd a = if odd b then gcd (min a b) (abs (halve (a - b))) else gcd a (halve b)
gcd' 1 _ c = (1,c+1)
gcd' a b c | a == b = (a,c+1)
| even a = if even b then fstapp (2*) (gcd' (halve a) (halve b) (c+1))
else gcd' a (halve b) (c+1)
| odd a = if odd b then gcd' (min a b) (abs (halve (a - b))) (c+1)
else gcd' a (halve b) (c+1)
fstapp f (x,y) = (f x,y)
|
186 #4590() Rating0/8=0.00
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
1 reply [ reply ]