Exercise 1.19: There is a clever algorithm for
computing the Fibonacci numbers in a logarithmic number of steps. Recall the
transformation of the state variables a and b in the fib-iter
process of 1.2.2: a
←
a
+
b and b
←
a.
Call this transformation T, and observe that applying T over and over
again n times, starting with 1 and 0, produces the pair Fib
(
n
+
1
) and
Fib
(
n
). In other words, the Fibonacci numbers are produced
by applying T
n, the n
th power of the transformation T,
starting with the pair (1, 0). Now consider T to be the special case of
p
=
0 and q
=
1 in a family of transformations T
p
q,
where T
p
q transforms the pair (
a
,
b
) according to
a
←
b
q
+
a
q
+
a
p and b
←
b
p
+
a
q.
Show that if we apply such a transformation T
p
q twice, the
effect is the same as using a single transformation T
p
′
q
′ of the
same form, and compute p
′ and q
′ in terms of p and q. This
gives us an explicit way to square these transformations, and thus we can
compute T
n using successive squaring, as in the fast-expt
procedure. Put this all together to complete the following procedure, which
runs in a logarithmic number of steps:
(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
⟨??⟩ ;compute p'
⟨??⟩ ;compute q'
(/ count 2)))
(else
(fib-iter (+ (* b q)
(* a q)
(* a p))
(+ (* b p)
(* a q))
p
q
(- count 1)))))
练习 1.19：有一个巧妙的算法可以在对数步骤数内计算斐波那契数。回忆 1.2.2 节 fib-iter 计算过程中状态变量 a 和 b 的变换：a ← a + b，b ← a。将这一变换称为 T，可以观察到：从 1 和 0 出发，将 T 反复应用 n 次，得到的序对就是 Fib(n+1) 和 Fib(n)。换言之，斐波那契数是从序对 (1, 0) 出发，对变换 T 的 n 次幂 Tⁿ 求值所得到的结果。现在把 T 看作变换族 T_pq 中 p = 0、q = 1 的特殊情形，其中 T_pq 对序对 (a, b) 的变换规则为：a ← bq + aq + ap，b ← bp + aq。请证明：对变换 T_pq 应用两次，效果等同于应用一次同族中的某个变换 T_p'q'，并根据 p 和 q 求出 p' 和 q'。这就给出了对这些变换进行平方的显式方法，从而可以像 fast-expt 过程那样用逐次平方来计算 Tⁿ。将上述思路整合起来，补全以下过程（该过程运行步骤数为对数级）：
(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
⟨??⟩ ;compute p'
⟨??⟩ ;compute q'
(/ count 2)))
(else
(fib-iter (+ (* b q)
(* a q)
(* a p))
(+ (* b p)
(* a q))
p
q
(- count 1)))))
(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
⟨??⟩ ;compute p'
⟨??⟩ ;compute q'
(/ count 2)))
(else
(fib-iter (+ (* b q)
(* a q)
(* a p))
(+ (* b p)
(* a q))
p
q
(- count 1)))))