; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 计算机程序的构造和解释(习题试解)
;
; created: code17 02/28/05
; modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================
;; SICP No.1.19
;; 本题为理解题
;; T以pq为参数的目的，使得T^2和T之间的关系可以通过pq值的函数关系来刻画
;; T^2_(pq) (a,b) = T_(pq) (T_(pq) (a,b)) = T_(pq) (bq+aq+ap,bp+aq)
;; = (bpq + aq^2 + bq^2 + aq^2 + apg + bpq + apq + ap^2 ,
;; bp^2 + apq + bq^2 + aq^2 + apq)
;; = ( b(2pq + q^2) + a(2pq + q^2) + a(p^2 + q^2) ,
;; b(p^2 + q^2) + a(2pq + q^2) )
;; = (bq'+aq'+ap, bp'+aq') (设p'=p^2+q^2, q'=2pq+q^2)
;; = T_(p'q') (a,b)
;; 所以T^2与T之间存在参数上的函数关系，T^n则可简单转化为T^(n/2)的
;; 对应操作。程序如下
(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)))))
(define (even? x)
(= (remainder x 2) 0))
;; Test-it:
;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc.
;; > (fib 2)
;; 1
;; > (fib 3)
;; 2
;; > (fib 4)
;; 3
;; > (fib 5)
;; 5
;; > (fib 6)
;; 8
;; > (fib 8)
;; 21
;; > (fib 10)
;; 55
;; >
;; 如果明白关键是找出T^2和T之间的参数上的函数关系，我们可以构造自己
;; 的表示方法。设S为T,T^2,T^3...中的任一操作
;; 若S(a,b) = (x1*a+y1*b, x2*a+y2*b)
;; 则S^2(a,b) = (x1(x1*a+y1*b)+y1(x2*a+y2*b), x2(x1*a+y1*b)+y2(x2*a+y2*b))
;; = ((x1^2+x2y1)a+(x1y1+y1y2)b, (x1x2+x2y2)a+(x2y1+y2^2)b)
;; 以(x1,x2,y1,y2)代表S的参数配置，则S^2的配置为
;; ((x1^2+x2y1), (x1y1+y1y2), (x1x2+x2y2), (x2y1+y2^2))
;; 例如，因为T(a,b)=(a+b,a)，因此T的参数配置为(1,1,1,0)
;; 通过以上公式可算得T^2的参数配置为(2,1,1,1)
;; 因此任何T^n操作均可递归至T^(n/2)通过参数的运算
;; 程序如下
(define (fib n)
(fib-iter 1 0 1 1 1 0 n))
(define (fib-iter a b x1 y1 x2 y2 count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (* x1 x1) (* x2 y1))
(+ (* x1 y1) (* y1 y2))
(+ (* x1 x2) (* x2 y2))
(+ (* x2 y1) (* y2 y2))
(/ count 2)))
(else (fib-iter (+ (* x1 a) (* y1 b))
(+ (* x2 a) (* y2 b))
x1
y1
x2
y2
(- count 1)))))
;; 测试结果与课本的程序结果完全一致
;; 课本里给出的方案是两个参数pq，我们这里是4个，说明这4个参数有相关性，可以消去
;; 但课本的方案的问题在于没有交待这个pq模型是怎么得到的，而这里的方案的参数含义
;; 直观明了，更容易理解。