不知道如何解决 SICP 练习 1.11

Question

练习1.11：

函数f由以下规则定义：如果n f(n) = n 3 且如果 n > 则 f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) 3..编写一个通过递归过程计算 f 的过程。编写一个通过迭代过程计算 f 的过程。

递归地实现它非常简单。但我不知道如何迭代地做到这一点。我尝试与给出的斐波那契示例进行比较，但我不知道如何使用它作为类比。所以我放弃了（为我感到羞耻）并在 Google 上搜索解释，我发现了这一点：

(define (f n)
   (if (< n 3)
       n
       (f-iter 2 1 0 n)))

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

读完之后，我了解了代码及其工作原理。但我不明白的是从函数的递归定义到此所需的过程。我不明白代码是如何在某人的头脑中形成的。

您能解释一下达成解决方案所需的思维过程吗？

Answer 1

您需要捕获某些累加器中的状态并在每次迭代时更新状态。

如果您有使用命令式语言的经验，请想象编写一个 while 循环并在循环的每次迭代期间跟踪变量中的信息。你需要什么变量？您将如何更新它们？这正是您在Scheme 中进行迭代（尾递归）调用集所必须要做的。

换句话说，开始将其视为 while 循环而不是递归定义可能会有所帮助。最终你会足够流利地使用递归 ->迭代转换，您不需要额外的帮助即可开始。

---

对于这个特定的示例，您必须仔细查看三个函数调用，因为并不能立即清楚如何表示它们。然而，这是可能的思考过程：（在Python伪代码中强调命令性）

每个递归步骤都会跟踪三件事：

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) 

所以我需要三个状态来跟踪 的当前值、最后一个值和倒数第二个值f。 （即 f(n-1)、f(n-2) 和 f(n-3)。）将它们称为 a、b、c。我必须在每个循环内更新这些部分：

for _ in 2..n:
    a = NEWVALUE
    b = a
    c = b
return a

那么 NEWVALUE 是什么？好吧，现在我们有了 f(n-1)、f(n-2) 和 f(n-3) 的表示，这只是递归方程：

for _ in 2..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

现在剩下的就是弄清楚a、b 和 c 的初始值。但这很容易，因为我们知道如果 n f(n) = n 3..

if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

这与Scheme迭代版本还是有点不同，但我希望你现在能看到这个思考过程。

Answer 2

我认为您是在问人们如何在“设计模式”之外自然地发现算法。

查看 f(n) 在每个 n 值处的展开对我很有帮助：

f(0) = 0  |
f(1) = 1  | all known values
f(2) = 2  |

f(3) = f(2) + 2f(1) + 3f(0)
f(4) = f(3) + 2f(2) + 3f(1)
f(5) = f(4) + 2f(3) + 3f(2)
f(6) = f(5) + 2f(4) + 3f(3)

仔细观察 f(3)，我们发现我们可以立即根据已知值计算它。
我们需要什么来计算 f(4)？

我们至少需要计算 f(3) + [其余部分]。但是当我们计算 f(3) 时，我们也会计算 f(2) 和 f(1)，而我们恰好需要这些来计算 f(4) 的[其余部分]。

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)

因此，对于任何数字 n，我可以从计算 f(3) 开始，然后重用用于计算 f(3) 的值来计算 f(4)...并且该模式继续...

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)
            ↘       ↘
f(5) = f(4) + 2f(3) + 3f(2)

因为我们将重用它们，让我们给它们命名 a、b、c。以我们正在进行的步骤为下标，并进行 f(5) 的计算：

  Step 1:    f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a1 + 2b1 +3c1

其中

a₁ = f(2) = 2,

b₁ = f(1 ) = 1,

c₁ = 0

因为 f(n) = n (n ₁) 3.

因此：

f(3) = a₁ + 2b₁ + 3c₁ = 4

  Step 2:  f(4) = f(3) + 2a1 + 3b1

因此：

a₂ = f(3) = 4（在上面步骤 1 中计算），

b₂ = a₁ = f(2) = 2,

c₂ sub> = b₁ = f(1) = 1

因此：

f(4) = 4 + 2*2 + 3*1 = 11

  Step 3:  f(5) = f(4) + 2a2 + 3b2

因此：

a₃ = f (4) = 11（在上面的步骤 2 中计算），

b₃ = a₂ = f(3) = 4,

c₃ = b₂ = f(2) = 2

因此：

f(5) = 11 + 2*4 + 3*2 = 25

在整个上述计算中，我们捕获先前计算中的状态并将其传递给下一步，
特别是：

a_step = 步骤结果 - 1

b_step = a_{step - 1}

c_step = b< sub>step -1

一旦我看到这个，那么想出迭代版本就很简单了。

Answer 3

由于您链接的帖子描述了很多有关解决方案的信息，因此我将尝试仅提供补充信息。

您尝试在此处的方案中定义尾递归函数，并给出（非尾）递归定义。

递归的基本情况（如果 n < 3，则 f(n) = n）由两个函数处理。我不太确定作者为什么这样做；第一个函数可以简单地是：

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

一般形式是：

(define (f-iter ... n)
   (if (base-case? n)
       base-result
       (f-iter ...)))

注意，我还没有填写 f-iter 的参数，因为您首先需要了解需要将什么状态从一个迭代传递到另一个迭代。

现在，让我们看看 f(n) 的递归形式的依赖关系。它引用 f(n - 1)、f(n - 2) 和 f(n - 3)，因此我们需要保留这些值。当然，我们需要 n 本身的值，这样我们就可以停止对其进行迭代。

这就是尾递归调用的方式：我们计算 f(n) 以用作 f(n - 1)，将 f(n - 1) 旋转为 f(n - 2) 和 f(n - 2)到 f(n - 3)，并递减计数。

如果这仍然没有帮助，请尝试问一个更具体的问题——当你写“我不明白”时，考虑到已经有相对详尽的解释，真的很难回答。

Answer 4

我将采用与此处其他答案略有不同的方法来解决此问题，重点关注编码风格如何使此类算法背后的思维过程更容易理解。

比尔的方法的麻烦，在你的问题中引用的问题是，目前尚不清楚状态变量 a、b 和 c 所传达的含义 。他们的名字没有传达任何信息，比尔的帖子也没有描述他们遵守的任何不变规则或其他规则。我发现如果状态变量遵循一些描述它们彼此关系的记录规则，那么制定和理解迭代算法就更容易。

考虑到这一点，请考虑完全相同算法的替代公式，它与 Bill 的不同之处仅在于为 a、b 和 c< 提供了更有意义的变量名称。 /code> 和一个递增的计数器变量而不是递减的计数器变量：

(define (f n)
    (if (< n 3)
        n
        (f-iter n 2 0 1 2)))

(define (f-iter n 
                i 
                f-of-i-minus-2
                f-of-i-minus-1
                f-of-i)
    (if (= i n)
        f-of-i
        (f-iter n
                (+ i 1)
                f-of-i-minus-1
                f-of-i
                (+ f-of-i
                   (* 2 f-of-i-minus-1)
                   (* 3 f-of-i-minus-2)))))

突然间，算法的正确性以及其创建背后的思维过程变得很容易看到和描述。计算 f(n)：

• 我们有一个计数器变量 i，它从 2 开始，逐渐增加到 n，每次调用时加 1 f-iter。
• 在此过程中的每一步，我们都会跟踪 f(i)、f(i-1) 和 f(i-2) ，这足以让我们计算f(i+1)。
• 一旦i=n，我们就完成了。

Answer 5

对我有帮助的是使用铅笔手动运行该流程，并使用作者为斐波那契示例提供的提示

a <- a + b
b <- a

将其转化为新问题是如何在流程中推动状态

a <- a + (b * 2) + (c * 3)
b <- a
c <- b

因此您需要一个带有接口的函数来接受3个变量：a、b、c。并且它需要使用上面的过程来调用自身。

(define (f-iter a b c)
  (f-iter (+ a (* b 2) (* c 3)) a b))

如果您运行并打印以 (f-iter 1 0 0) 开头的每次迭代的每个变量，您将得到类似这样的结果（当然它将永远运行）：

a   b   c
=========
1   0   0
1   1   0
3   1   1
8   3   1
17  8   3
42  17  8
100 42  17
235 100 42
...

你能看到答案吗？您可以通过对每次迭代的 b 列和 c 列求和来得到它。我必须承认我通过一些尝试和错误找到了它。剩下的唯一的事情就是有一个计数器来知道何时停止，这就是整个事情：

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

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

Answer 6

函数f由以下规则定义：f(n) = n，如果n<3且f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)，如果 n > 1) 3..编写一个通过递归过程计算 f 的过程。

已经写好了：

f(n) = n,                                  (* if *)  n < 3
     = f(n - 1) + 2f(n - 2) + 3f(n - 3),   (* if *)  n > 3

不管你信不信，曾经有这样一种语言< /a>.用另一种语言写下来只是语法问题。顺便说一句，您（错误）引用的定义有一个错误，现在非常明显且清晰。

编写一个通过迭代过程计算 f 的过程。

迭代意味着前进（有 你的解释！）而不是首先向后递归到最低级别，然后在返回的过程中向前计算结果：

f(0)   =  0
f(1)   =  1
f(2)   =  2
f(n)   =  f(n - 1) + 2f(n - 2) + 3f(n - 3) 
       =  a        + 2b        + 3c
f(n+1) =  f(n    ) + 2f(n - 1) + 3f(n - 2)
       =  a'       + 2b'       + 3c'         where
                                             a' = f(n) = a+2b+3c, 
                                             b' = f(n-1) = a, 
                                             c' = f(n-2) = b
......

因此，这将问题的状态转换描述为

 (n, a, b, c)  ->  (n+1, a+2*b+3*c, a, b)

我们可以将其编码为，

g (n, a, b, c) = g (n+1, a+2*b+3*c, a, b)

但它当然永远不会停止。因此，我们必须改为拥有

f n = g (2, 2, 1, 0)
  where
  g (k, a, b, c) = g (k+1, a+2*b+3*c, a, b),    (* if *) k < n
  g (k, a, b, c) = a,                           otherwise 

，并且这已经与您询问的代码完全相同，就语法而言。

在这里，按照我们的“前进”范式，向上计数到 n 更自然，但是像您引用的代码那样向下计数到 0 当然是完全等效的。

极端情况和可能的相差一错误将作为练习无趣的技术细节而被忽略。