最大公約数（除算禁止）
Posted feedbacks - Common Lisp
kozima
#4793()
[
Common Lisp
]
gcd は組み込みで存在しますが、こんな式を基に書いてみました。呼び出し回数 1937 回。
- gcd(x,x) = x
- gcd(2x+1, 2y+1) = gcd(2x+1, x-y)
- gcd(2x+1, 2y) = gcd(2x+1, y)
- gcd(2x, 2y) = 2*gcd(x, y)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | (defun *gcd (x y &optional (acc 1) (count 0))
(incf count)
(cond ((= x y)
(values count (* acc x)))
((and (oddp x) (oddp y)) ; odd, odd
(*gcd (min x y) (ash (abs (- x y)) -1) acc count))
((oddp x) ; odd, even
(*gcd x (ash y -1) acc count))
((oddp y) ; even, odd
(*gcd (ash x -1) y acc count))
(t ; even, even
(*gcd (ash x -1) (ash y -1) (ash acc 1) count))))
(defun fib (x)
(loop with l = '(1 1) for i from 2 to x
do (push (+ (car l) (cadr l)) l)
finally (return (car l))))
(format t "~{Called ~D times, result is ~D~}"
(multiple-value-list (*gcd (fib 2000) (fib 1999))))
|
186 #4590() Rating0/8=0.00
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
1 reply [ reply ]