2

我在 Lisp 中为 SICP 代码提供了这个解决方案：

 ;; ex 1.11. Iterative implementation 

 (define (f n) 
   (define (iter a b c count) 
     (if (= count 0) 
       a 
       (iter b c (+ c (* 2 b) (* 3 a)) (- count 1)))) 
   (iter 0 1 2 n))

我真的不知道 Lisp 是如何工作的。我在这里理解了一些东西，但是我仍然很难将它翻译成 Python。例如，我不知道为什么a写在下面if。这段代码如何翻译成 Python 或 C++？（函数必须是迭代的而不是递归的）

4

3 回答 3

4

有两种方法可以考虑翻译。一种是在不尊重 Python 的习惯用法和约定的情况下编写一个字面的、直接的翻译——它看起来像这样：

def f(n):
    def iter(a, b, c, count):
        if count == 0:
            return a
        else:
            return iter(b, c, 2*b + 3*a + c, count-1)
    return iter(0, 1, 2, n)

另一种方法是以 Python 风格编写代码，使其尊重目标语言的约定并利用其迭代机制：

def f(n):
    a, b, c = 0, 1, 2
    for count in range(n):
        a, b, c = b, c, 2*b + 3*a + c
    return a

顺便说一下，第二个版本会更快，并且不会出现堆栈溢出错误的问题（Python没有针对递归进行优化！）。在递归版本count中从nto0和在循环版本count中从0to是无关紧要的，因为无论如何除了迭代给定次数之外n，该值没有被用于任何事情。count

于 2013-10-24T22:30:48.037 回答
2

让我们看一下这段代码：

;; ex 1.11. Iterative implementation 

(define (f n) 
  (define (iter a b c count) 
    (if (= count 0) 
      a 
      (iter b c (+ c (* 2 b) (* 3 a)) (- count 1)))) 
  (iter 0 1 2 n))

这里首先要注意的是定义了两个函数。一个是f，另一个是iter。 iter是一个辅助函数，并且仅供f(因为它是在内部定义的f。没有理由不能将这两个定义分开为：

(define (iter a b c count) 
  (if (= count 0) 
    a 
    (iter b c (+ c (* 2 b) (* 3 a)) (- count 1))))

(define (f n) 
  (iter 0 1 2 n))

在 Lisps 中，语法(frob bar1 bar2 ...)意味着您正在frob使用参数调用函数bar1, bar2, ...。所以定义f

(define (f n) 
  (iter 0 1 2 n))

应该比较清楚。您正在定义一个f带有单个参数的函数n，然后您iter使用四个参数调用该函数0， , 1,2和n。那么做iter什么呢？

(define (iter a b c count) 
  (if (= count 0) 
    a 
    (iter b c (+ c (* 2 b) (* 3 a)) (- count 1))))

iter接受四个参数。首先，它检查是否count是0。如果是，则iter返回a。否则，使用,iter递归调用自身。和返回递归调用返回的值。根据上面对 Lisp 语法的描述，你应该可以看出这只是数学表达式c + 2b + 3a，也就是count-1。bc(+ c (* 2 b) (* 3 a))(- count 1)(+ c (* 2 b) (* 3 a))(- count 1)

我想，所有这一切中最棘手的部分是知道它if需要三个参数：第一个是测试表达式；第二个是“then”部分，也称为consequent；第三个是“else”部分，也称为alternative。与其他一些if仅用于有条件地执行某些语句的语言不同，它在 Lisp 中(if ...)返回一个值，该值要么是结果的值，要么是替代的值，这取决于测试的值是真还是假.

有了这个描述，您应该能够用您熟悉的任何编程语言编写对应的内容。

当然，一旦你理解了所有这些，你可能会很好地阅读Chris Rathman 将 SICP 代码翻译成 Python 的一些内容，其中包括对练习 1.11 中代码的翻译：

# Exercise 1.11
def f(n):
   if n < 3:
      return n
   else:
      return f(n-1) + 2*f(n-2) + 3*f(n-3)
def f_iter(a, b, c, count):
   if count == 0:
      return c
   else:
      return f_iter(a + 2*b + 3*c, a, b, count-1)
def f(n):
   return f_iter(2, 1, 0, n)
于 2013-10-24T20:09:37.323 回答
1

这基本上是iter在C中的样子

int iter (int a, int b, int c, int count)
{
    if( count == 0 )
       return a;
    else
       return iter(b, c, c + (2 * b) + (3 * a), count - 1);
}

Scheme 中的每个表达式都计算为一个值，因此它是隐式返回。if无论分支运行什么，iter 都返回，if 返回的则返回，依此类推。

在不确定的情况下，这看起来像是一个递归序列，它引用前 3 个数字来计算下一个在 Scheme 中迭代到常量堆栈的数字。请注意，Python 不会尾调用对此进行优化，而 C++ 和 C 可能需要特殊的编译器选项和有能力的编译器来做到这一点。

于 2013-10-24T19:51:47.100 回答