小编nat*_*ate的帖子

SICP 3.57的真正答案是什么

SICP练习3.57:当我们根据加流过程使用fib的定义来计算第n个斐波那契数时,要执行多少次加法运算?证明如果不使用3.5.1中描述的备忘录过程提供的优化而简单地将(delay?exp?)实现为(lambda()?exp?),加法运算的数量将成倍增加。

在线上有许多解决方案。大多数人声称,fib序列的非优化备忘-proc序列版本与计算非存储的常规fib函数相同。当跟踪未优化的备忘版本时,我看到了一个不同的故事。

令A(n)为(stream-ref fibs n)执行的加法数

  • A(0)= 0
  • A(1)= 0
  • A(2)= 1
  • A(3)= 3
  • A(4)= 7
  • A(5)= 14
  • A(6)= 26

当在非优化(非存储流)上使用替换和函数定义时,我可以确切地看到这些加法是什么以及为什么会发生这些加法,但是我很难提出一个好的方程式来回答实际上是指数的。

例如,针对A(4)跟踪的加法为:

  • 1 + 0
  • 1 + 0
  • 1 + 1
  • 1 + 0
  • 1 + 1
  • 1 + 0
  • 2 + 1

这是一些伪代码,用于显示(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)

lisp scheme sicp lazy-sequences racket

6
推荐指数
1
解决办法
93
查看次数

标签 统计

lazy-sequences ×1

lisp ×1

racket ×1

scheme ×1

sicp ×1