SICP 练习 1.19，转换

Question

来自计算机程序的结构和实现，第二版：

练习1.19：有一种巧妙的算法可以以对数步数计算斐波那契数。
回想一下

fib-iter

中状态变量 a 和 b 的变换 第1-2-2节的过程：

a ← a + b

和

b ← a

。 打电话给这个 变换 T，并观察一遍又一遍地应用 T n 次，从 1 和 0 开始，产生对 Fib(n + 1) 和 Fib(n)。
换句话说，斐波那契数是通过应用 Tⁿ（变换 T 的 n 次方）生成的，从 对 (1,0)。
现在考虑 T 是

p = 0

和

q = 1

的特例 在一系列变换 T_pq 中，其中 T_pq 变换 根据

a ← bq + aq + ap

和

b ← bp + aq

配对 (a,b)。
证明 如果我们应用这样的变换 T_pq 两次，效果是相同的 使用相同形式的单个变换 T_p'q'，并且 根据 p 和 q 计算 p' 和 q'。
这给了我们一个明确的方法 对这些变换进行平方，因此我们可以使用以下方法计算 T^n 连续平方，如

fast-expt

程序中所示。
将这一切 一起完成以下过程，该过程在 对数步数：(5)

(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)))))

(5) 这项练习是 Joe Stoy 根据 Kaldewaij 1990 中的示例向我们建议的。

我不知道从哪里开始，我很困惑。 T 是完全不同且涉及两个额外变量的变换的“特例”吗？ （嗯，它说这是“变换系列”的“特例”，我猜这些都是我不知道的数学术语，而且我找不到任何定义。）

另外，显然如果你用 p 和 q 来变换 a 和 b 一次，根据 a ← bq + aq + ap 和 b ← bp + aq，a 成为斐波那契数列中的下一个数字（而 b 保存 a 的前一个值） ，就像原始的

fib-iter

过程一样，但是如果您应用变换两次，您可以将获得所需值所需的步骤数减半斐波那契数列？！

考虑到这一切，我完全不知道 p' 和 q' 应该是什么；我的意思是，从文本和代码来看，我必须假设 p' 和 q' 是 p 和 q 的值，当用于转换 a 和 b 时，最终会使它们在 b 的途中变成一半斐波那契数列中的期望值（以及之后的值），但我不仅不知道如何开始计算 p' 和 q' 的方法，我也不明白如何转换 a ← bq + aq + ap当你应用一次时，b ← bp + aq 应该相当于 a ← a + b 和 b ← a，但当你应用两次时，则完全不同。

（我认为“应用变换两次”实际上一定意味着与“平方变换”有关，我可以在网上找到一些内容说“T²(x)=T(T(x))”，这并不意味着在这里真的很有帮助，因为 T_(pq) 只变换对 (a,b) 并且我应该弄清楚如何从 p 和 q 计算 p' 和 q'...如果我在咆哮，请告诉我错误的树，在这里。）

无论如何，我想我的心理工具箱中一定缺少一些工具来理解这些，所以请让我知道它们是什么。请不要给我练习的答案，或直接描述如何计算 p' 和 q'；我正在努力正确地读完这本书。我只需要知道什么是我应该理解的，什么是我不应该理解的。谢谢。

Answer 1

您可能需要一些线性代数，特别是矩阵乘法。

然后，您可以将菲诺卡奇序列的迭代生成写为状态向量与变换矩阵

T

的重复相乘，并利用乘法的结合性将

T*(T*x)

重写为

(T*T)*x

。