不知道如何解决SICP练习1.11 [英] No idea how to solve SICP exercise 1.11

问题描述

练习1.11 ：

函数 f 由<$ c $规则定义c> f（n）= n 如果 n< 3 和 f（n）= f（n - 1）+ 2f（n - 2）+ 3f（n - 3）如果 n> 3 。编写一个通过递归过程计算 f 的过程。编写一个通过迭代过程计算 f 的过程。

A function f is defined by the rule that f(n) = n if n < 3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n > 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

递归实现它很简单。但我无法弄清楚如何迭代地做到这一点。我尝试与给出的Fibonacci示例进行比较，但我不知道如何使用它作为类比。所以我放弃了（羞辱我）并用Google搜索解释，我发现了这个：

Implementing it recursively is simple enough. But I couldn't figure out how to do it iteratively. I tried comparing with the Fibonacci example given, but I didn't know how to use it as an analogy. So I gave up (shame on me) and Googled for an explanation, and I found this:

(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))))

阅读后，我理解代码及其工作原理。但我不明白的是从函数的递归定义到此需要的过程。我不明白代码是如何形成的。

After reading it, I understand the code and how it works. But what I don't understand is the process needed to get from the recursive definition of the function to this. I don't get how the code could have formed in someone's head.

你能解释一下解决方案所需的思考过程吗？

Could you explain the thought process needed to arrive at the solution?

推荐答案

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

You need to capture the state in some accumulators and update the state at each iteration.

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

If you have experience in an imperative language, imagine writing a while loop and tracking information in variables during each iteration of the loop. What variables would you need? How would you update them? That's exactly what you have to do to make an iterative (tail-recursive) set of calls in Scheme.

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

In other words, it might help to start thinking of this as a while loop instead of a recursive definition. Eventually you'll be fluent enough with recursive -> iterative transformations that you won't need to extra help to get started.

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

For this particular example, you have to look closely at the three function calls, because it's not immediately clear how to represent them. However, here's the likely thought process: (in Python pseudo-code to emphasise the imperativeness)

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

Each recursive step keeps track of three things:

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

所以我需要三个状态来跟踪 f 。 （即 f（n-1），f（n-2）和f（n-3）。）将它们称为 a，b ，c 。我必须在每个循环中更新这些部分：

So I need three pieces of state to track the current, the last and the penultimate values of f. (that is, f(n-1), f(n-2) and f(n-3).) Call them a, b, c. I have to update these pieces inside each loop:

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

那么什么是NEWVALUE？那么，现在我们有 f（n-1），f（n-2）和f（n-3）的表示，它只是递归方程：

So what's NEWVALUE? Well, now that we have representations of f(n-1), f(n-2) and f(n-3), it's just the recursive equation:

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

现在剩下的就是找出初始值 a，b和c 。但这很容易，因为我们知道 f（n）= n，如果n< 3 。

Now all that's left is to figure out the initial values of a, b and c. But that's easy, since we know that f(n) = n if 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迭代版本略有不同，但我希望你能看到这个想法现在处理。

That's still a little different from the Scheme iterative version, but I hope you can see the thought process now.

这篇关于不知道如何解决SICP练习1.11的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！