最大公約数（除算禁止）
Posted feedbacks - Scheme
引き算のみで。
Z80マシン語で遊んでいたころ、除算を使わないでもこれでgcdが計算できることに気づいて大発見をしたような気分になりました。後でよく考えたらユークリッドの互除法を非効率にやっているだけでした。
隣り合うフィボナッチ数の場合は実は減算法でもあまり効率が悪くなりません。常に差がひとつ前のフィボナッチ数になるわけですから。
gosh> (time (gcd-nodiv (fib 2000) (fib 1999)))
;(time (gcd-nodiv (fib 2000) (fib 1999)))
; real 0.002
; user 0.000
; sys 0.000
1
ループ回数は互除法でやった場合と同じになります。
gosh> (gcd-nodiv/cnt (fib 2000) (fib 1999) 1)
1
1998
実はこの引数の場合は、組み込みのgcd (互除法使用) の方が遅かったりします。bignumの除算が重いんじゃないかな。
gosh> (time (gcd (fib 2000) (fib 1999)))
;(time (gcd (fib 2000) (fib 1999)))
; real 0.014
; user 0.010
; sys 0.000
1
Z80マシン語で遊んでいたころ、除算を使わないでもこれでgcdが計算できることに気づいて大発見をしたような気分になりました。後でよく考えたらユークリッドの互除法を非効率にやっているだけでした。
隣り合うフィボナッチ数の場合は実は減算法でもあまり効率が悪くなりません。常に差がひとつ前のフィボナッチ数になるわけですから。
gosh> (time (gcd-nodiv (fib 2000) (fib 1999)))
;(time (gcd-nodiv (fib 2000) (fib 1999)))
; real 0.002
; user 0.000
; sys 0.000
1
ループ回数は互除法でやった場合と同じになります。
gosh> (gcd-nodiv/cnt (fib 2000) (fib 1999) 1)
1
1998
実はこの引数の場合は、組み込みのgcd (互除法使用) の方が遅かったりします。bignumの除算が重いんじゃないかな。
gosh> (time (gcd (fib 2000) (fib 1999)))
;(time (gcd (fib 2000) (fib 1999)))
; real 0.014
; user 0.010
; sys 0.000
1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | (define (gcd-nodiv m n)
(cond [(= n m) n]
[(or (= m 1) (= n 1)) 1]
[(> m n) (gcd-nodiv n (- m n))]
[else (gcd-nodiv m (- n m))]))
;;
;; 以下は測定用
;;
;;ループ回数のカウント
(define (gcd-nodiv/cnt m n cnt)
(cond [(= n m) (values n cnt)]
[(or (= m 1) (= n 1)) (values 1 cnt)]
[(> m n) (gcd-nodiv/cnt n (- m n) (+ cnt 1))]
[else (gcd-nodiv/cnt m (- n m) (+ cnt 1))]))
;;メモワイズ版fib
(define fib
(let1 memo (make-hash-table 'eqv?)
(lambda (n)
(cond [(<= n 2) 1]
[(hash-table-get memo n #f)]
[else (let1 val (+ (fib (- n 1)) (fib (- n 2)))
(hash-table-put! memo n val)
val)]))))
|
186 #4590() Rating0/8=0.00
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
1 reply [ reply ]