2

我正在尝试扩展一个简单的斐波那契函数，并且我需要多次使用每个术语的值。所以，我想我会let用来坚持价值观。但是，我没有得到我认为应该从函数中得到的东西。

这是原始fib功能：

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

这是我做同样事情的尝试，但是let：

(define (fib-with-let n)
  (if (< n 2)
      0
      (let ((f1 (fib-with-let (- n 1)))
            (f2 (fib-with-let (- n 2))))
        (+ f1 f2))))

结果：

> (fib 10)
55
> (fib-with-let 10)
0

谢谢！

4

4 回答 4

7

你打错了：

(if (< n 2)
    0
    ...)

你的意思是n。

于 2011-06-16T18:51:22.353 回答
6

你打错了你的基本情况。在您拥有的第一个版本中：

(if (< n 2)
      n

但是在您的后一个版本中，您写道：

(if (< n 2)
      0

所以只需更改0为n.

于 2011-06-16T18:52:58.777 回答
2

你的 let 并没有真正做任何事情。您仍在进行所有额外的计算。仅仅因为您定义f1为(fib-with-let (- n 1))并不意味着您不会再次计算 n-1 的 fib。f2不使用。_ f1如果你想f2看到你 f1会使用let*. 但是，即使这也不是您真正想要的。

作为证据，以下是运行时间for fib(35)和fib-with-let(35)：

(time (fib 35))
cpu time: 6824 real time: 6880 gc time: 0
(time (fib-with-let 35))
cpu time: 6779 real time: 6862 gc time: 0

为了避免额外的计算，您真正想要做的是使用动态编程并以自下而上的方式递归。

你想要的是以下代码：

(define (dynprog-fib n)
  (if (< n 2)
      n
      (dynprog-fib-helper 1 1 2 n)))

(define (dynprog-fib-helper n1 n2 current target)
  (if (= current target)
      n2
      (dynprog-fib-helper n2 (+ n1 n2) (add1 current) target)))

(time (dynprog-fib 35))
cpu time: 0 real time: 0 gc time: 0
(time (dynprog-fib 150000))
cpu time: 2336 real time: 2471 gc time: 644

如您所见，您可以在幼稚方法所用时间的三分之一内完成前 150,000 个谎言。

因为看起来您对 let 的作用感到困惑，所以让我更好地说明：

当你说：

(let ((a 1)
      (b 2))
  (+ a b))

您的意思是，让 a 为 1，b 为 2，将它们加在一起。如果你改为说：

(let ((a 1)
      (b (+ a 1))
  (+ a b))

你能猜到你会得到什么吗？不是 3. 它会被炸毁expand: unbound identifier in module in: a

简而言之let，您的作业不能互相看到。如果您想编写上述内容，则必须使用let*：

(let* ((a 1)
      (b (+ a 1))
  (+ a b))

那会给你你期望的3。let*本质上扩展为：

(let ((a 1))
     (let ((b (+ a 1)))
          (+ a b)))

你以为你在用 let 做的事情叫做memoization。这是一种存储中间值的技术，因此您不必重复它们。但是，Let 不会为您做到这一点。

于 2011-06-23T04:47:12.697 回答
0

尽管您的问题是fib-with-let函数中的拼写错误，但最简单的形式let是匿名 lambda 的“语法糖”，然后是参数，然后评估并传递给 Lamba，然后评估并返回最终值。所以

(let ((f1 (fib-with-let (- n 1)))
      (f2 (fib-with-let (- n 2))))
        (+ f1 f2))

会被重写而不let看起来像

((lambda (f1 f2) (+ f1 f2))(fib-with-let (- n 1))(fib-with-let (- n 2)))
于 2011-06-17T19:53:15.263 回答