2

我试图理解我为一个练习阅读的解决方案，该练习定义了一个对数时间过程，用于查找斐波那契数列中的第 n 个数字。问题是计算机程序的结构和解释 (SICP) 中的 1.19。

剧透警报：这个问题的解决方案将在下面讨论。

Fib(n) 可以按如下线性时间计算：从 a = 1 和 b = 0 开始。Fib(n) 始终等于 b 的值。因此，最初，当 n = 0 时，Fib(0) = 0。每次应用以下变换时，n 都会增加 1，Fib(n) 等于 b 的值。

   a <-- a + b
   b <-- a

为了在对数时间内做到这一点，问题描述将变换 T 定义为变换

a' <-- bq + aq + ap
b' <-- bp + aq

其中 p = 0 和 q = 1，最初，因此此转换与上述转换相同。

然后应用上述变换两次，练习指导我们用 a 和 b 的原始值来表示新的值 a'' 和 b''。

a'' <-- b'q + a'q + a'p = (2pq + q^2)b + (2pq + q^2)a + (p^2 + q^2)a
b' <-- b'p + a'q = (p^2 + q^2)b + (2pq + q^2)a

然后，该练习将这种应用两次变换的应用称为“对变换求平方”。我的理解正确吗？

本练习的解决方案应用了使用上述平方变换值的技术来生成以对数时间运行的解决方案。问题如何在对数时间内运行？在我看来，每次我们使用平方变换的结果时，我们都需要进行一次变换而不是两次。那么我们如何连续每次将步数减半呢？

来自 schemewiki.org 的解决方案发布在下面：

 (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 
                    (+ (square p) (square q)) 
                    (+ (* 2 p q) (square q)) 
                    (/ count 2))) 
         (else (fib-iter (+ (* b q) (* a q) (* a p)) 
                         (+ (* b p) (* a q)) 
                         p 
                         q 
                         (- count 1))))) 

 (define (square x) (* x x))
4

2 回答 2

1

然后，该练习将这种应用两次变换的应用称为“对变换求平方”。我的理解正确吗？

是的，对变换进行平方意味着应用两次，或者（如本练习的解决方案中的情况）找到另一个等效于应用两次的变换。

问题如何在对数时间内运行？在我看来，每次我们使用平方变换的结果时，我们都需要进行一次变换而不是两次。那么我们如何连续每次将步数减半呢？

对给定变换求平方使我们能够减少步数，因为平方变换中的p和q增长速度比原始变换中的要快得多。这类似于使用连续平方比重复乘法更快地计算指数的方式。

那么我们如何连续每次将步数减半呢？

这在给出的代码中。只要count是偶数，(/ count 2)就在下一次迭代中传递计数。无论n在初始迭代中传入什么值，它甚至会在交替迭代中（最坏情况）。

如果您想在本练习中逐步推导平方变换，可以阅读我关于SICP 练习 1.19：计算斐波那契数的博文。

于 2013-02-17T03:07:03.717 回答
0

@Bill-the-Lizard 提供了一个很好的证明，但是您允许自己对与变换有关的“两次”一词和“方形”一词的看法产生冲突。

a) 计算 T 项的两倍——即 T 的两倍——是乘法的一种情况。乘法的过程只是在每一步将 T 增加一个常数值的过程，其中常数值是原始项本身。

但相比之下：

b) 给定的斐波那契变换是一个需要在每个操作步骤使用项 T 的最新状态的过程（而不是使用一个常数值）。AND，操作公式不是一个简单的增量，而是实际上是一个二次表达式（即在每个连续步骤中都涉及平方）。

就像比尔说的那样，如果您在调试器中逐步执行这种连续的平方效应，它将变得非常清楚（每当我卡在某个地方时，我更喜欢手动计算一些简单的情况）。

换一种方式思考这个过程：

要到达目的地，如果您可以在下一步中走完当前距离的平方，但仍然设法花费固定的时间来完成每一步，那么您将比不断采取步骤更快地到达目的地，每个都在恒定时间内。

于 2013-04-06T06:34:46.490 回答