首页 > 其他 > 详细

SICP:1.19快速的求Fib数列

时间:2015-03-23 21:22:15      阅读:347      评论:0      收藏:0      [点我收藏+]
#lang racket

(define (fib n) 
  (fib-iter 1 0 0 1 n)
  );fib

(define (fib-iter a b p q count)
  (cond ((= count 0) b);0
    ((even? count)
     (fib-iter a
           b
           (+ (* p p) (* q q))
           (+ (* q q) (* 2 p q))
           (/ count 2)));even?
    (else (fib-iter (+ (* b q) (* a q) (* a p) );+
            (+ (* b p) (* a q) );+
                    p
            q
            (- count 1))
     );else
   );cond  
 );fib-iter

(define (even? n) 
  (= (remainder n 2)
     0)
  );even?

(fib 1)
(fib 2)
(fib 3)
(fib 4)
(fib 5)

;T(pq):(a,b)=>(bq+aq+ap, bp+aq)
;T(pq):(bq+aq+ap, bp+aq)=>((bp+aq)q + (bq+aq+ap)q + (bq+aq+ap)p,
;                          (bp+aq)p + (bq+aq+ap)q)
;      => (2bpq+2aqq+bqq+2apq+app, bpp+2apq+bqq+aqq)
;      => (b(2pq+qq)+a(2pq+qq)+a(qq+pp), b(qq+pp)+a(2pq+qq))
;q‘ = 2pq+qq
;p‘ = qq+pp
;

 

也可以使用矩阵的快速幂乘

SICP:1.19快速的求Fib数列

原文:http://www.cnblogs.com/wizzhangquan/p/4360968.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!