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

问题描述

练习 1.11:

函数 f 由 f(n) = n if 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.

递归实现它很简单.但我不知道如何迭代地做到这一点.我尝试与给出的斐波那契示例进行比较，但我不知道如何将其用作类比.所以我放弃了(对我感到羞耻)并在 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))))

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

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 if 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屋！