フィボナッチ数列をO(log N)で求めるプログラム。
行列をもとにした解法らしいんだけど、なんで動くのかちょっと不安。
(define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a b (+ (* p p) (* q q)) ; compute p' (+ (* 2 (* p q)) (* q q)) ; compute q' (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))参考になるかどうか・・・
No comments:
Post a Comment