SICP练习3.57:当我们根据加流过程使用fib的定义来计算第n个斐波那契数时,要执行多少次加法运算?证明如果不使用3.5.1中描述的备忘录过程提供的优化而简单地将(delay?exp?)实现为(lambda()?exp?),加法运算的数量将成倍增加。
在线上有许多解决方案。大多数人声称,fib序列的非优化备忘-proc序列版本与计算非存储的常规fib函数相同。当跟踪未优化的备忘版本时,我看到了一个不同的故事。
令A(n)为(stream-ref fibs n)执行的加法数
当在非优化(非存储流)上使用替换和函数定义时,我可以确切地看到这些加法是什么以及为什么会发生这些加法,但是我很难提出一个好的方程式来回答实际上是指数的。
例如,针对A(4)跟踪的加法为:
这是一些伪代码,用于显示(stream-ref fibs 4)的替换,其中“。” 代表中缀流约束,{e}代表承诺执行e。
(cddddr fibs)
(cddr (add-streams (cdr fibs) fibs))
(cddr (stream-map + (cdr fibs) fibs)))
(cddr ((+ 1 0) . {stream-map + (cddr fibs) (cdr fibs)}))
(cdr (stream-map + (cddr fibs) (cdr fibs)))
(cdr (stream-map + …Run Code Online (Sandbox Code Playgroud)