SICP 习题 (1.19) 解题总结

SICP习题1.19要求用对数步数求斐波那契数，有关斐波那契数我们在习题1.13 中讨论过，书中1.2.2节也详细讲解了斐波那契数的求法。在1.2.2节中讲述了斐波那契数的递归求法和迭代求法，其中递归求法的步数为Fib(n)，而迭代求法的步数相对于n是线性的。虽然迭代求法的步数已经很少了，但是我们可以通过一种方法将步数减少为对数步数，其中的关键就是前面习题中提到的，将两个连续变换转换成一次变换的方法。

在迭代求法中，关键是以下变换：

求出Fib(0)，令其为b1

求出Fib(1)，令其为a1

按斐波那契数定义，那么a1+b1就是Fib(2)

接着，令b2等于a1, a2等于a1+b1，那么a2+b2就是Fib(3)

如此一直变换，就可以通过a(n-1)+b(n-1)求出Fib(n)。

现在的关键就是找出将以上变换中的连续两次变换转换成一次变换的方法。

首先声明，这个让我自己想是打破脑袋都想不出来的，我是按书中题目的提示来的。

首先按我们总结的，

有等式1:

b2=a1
a2=a1+b1

接着按书上的提示，用等式2表达等式1：

等式2:

b2=b1p+a1q
a2=b1q+a1q+a1p

按等式2可以得到：

等式3:

b3=b2p+a2q
a3=b2q+a2q+a2p

将等式2代入等式3，有：

b3 = b2p+a2q = (b1p+a1q)p+(b1q+a1q+a1p)q 
=>b3 = b1pp + a1qp + b1qq + a1qq + a1pq
=>b3= b1(pp + qq)  +  a1 (qp + qq + pq)
=>b3= b1 (pp + qq) + a1 (qq + 2pq)

a3 = b2q+a2q+a2p = (b1p+a1q)q+(b1q+a1q+a1p)q+(b1q+a1q+a1p)p
=> a3= b1pq + a1qq + b1qq + a1qq + a1pq + b1qp + a1qp + a1pp
=> a3= b1 (pq + qq + qp) + a1(qq + qq +pq+ qp + pp)
=> a3= b1 (pq + qq + pq) + a1(qq + pp) + a1 (qq + pq + qp)
=> a3=b1(qq+2pq) + a1(qq + pp) + a1(qq +2pq)

令p2= (pp + qq) q2=(qq + 2pq)

则有：

b3=b1p2  + a1 q2
a3=b1q2 + a1 p2 + a1q2

所以p2= (pp + qq) q2=(qq + 2pq)是题解

将以上公式转换为代码填入题目准备好的过程主体，结果如下：

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