不知道如何解决SICP练习1.11

Question

练习1.11:

函数f由f(n) = nif n < 3和f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)if 的规则定义n > 3.编写一个f通过递归过程计算的过程.编写一个f通过迭代过程计算的过程.

递归地实现它很简单.但我无法弄清楚如何迭代地做到这一点.我尝试与给出的Fibonacci示例进行比较,但我不知道如何将其用作类比.所以我放弃了(羞辱我)并用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) and 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) and f(n-3),它只是递归方程式:

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

现在剩下的就是找出初始值a, b and c.但这很容易,因为我们知道这一点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迭代版本略有不同,但我希望你现在可以看到思考过程.

Answer 2

我想你问的是如何在"设计模式"之外自然地发现算法.

在每个n值处查看f(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 ₂ = 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

在上面的计算中,我们在前面的计算中捕获状态并将其传递给下一步,特别是:

一个_步骤步骤的结果= - 1

b _step = _步骤-1

c _step = b _{step -1}

一旦我看到这一点,那么提出迭代版本就很简单了.