30

练习 1.11：

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

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

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

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

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

4

6 回答 6

36

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

如果您有使用命令式语言的经验，想象一下编写一个 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迭代版还是有点区别的，但是希望你现在可以看到思路了。

于 2010-03-02T19:45:34.440 回答
20

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

查看 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)：

  第 1 步：f(3) = f(2) + 2f(1) + 3f(0) 或 f(3) = a 1 + 2b 1 +3c 1

在哪里

a 1 = f(2) = 2,

b 1 = f(1) = 1,

c 1 = 0

因为对于 n < 3，f(n) = n。

因此：

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

  第 2 步：f(4) = f(3) + 2a 1 + 3b 1

所以：

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

b 2 = a 1 = f(2) = 2,

c 2 = b 1 = f(1) = 1

因此：

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

  第 3 步：f(5) = f(4) + 2a 2 + 3b 2

所以：

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

b 3 = a 2 = f(3) = 4，

c 3 = b 2 = f(2) = 2

因此：

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

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

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

b步=一步 - 1

c步= b步 -1

一旦我看到这一点，然后想出迭代版本就很简单了。

于 2011-02-14T18:28:24.883 回答
4

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

在给定（非尾）递归定义的情况下，您正在尝试在 Scheme 中定义尾递归函数。

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

(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)，并递减计数。

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

于 2010-03-02T19:51:09.483 回答
3

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

您的问题中引用的Bill 方法的问题在于，状态变量 、 、 和 所传达的含义并不清楚。他们的名字没有传达任何信息，比尔的帖子也没有描述他们遵守的任何不变量或其他规则。如果状态变量遵循一些描述它们相互关系的记录规则，我发现更容易制定和理解迭代算法。abc

考虑到这一点，考虑完全相同算法的这种替代公式，它与比尔的不同之处仅在于具有更有意义的变量名称a，b以及c递增的计数器变量而不是递减的变量：

(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，我们就完成了。
于 2014-06-08T21:22:07.560 回答
1

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

已经写好了：

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

信不信由你，曾经有过这样的语言。用另一种语言写下来只是语法问题。顺便说一句，你（错误）引用它的定义有一个错误，现在非常明显和清楚。

编写一个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当然是完全等价的。

极端情况和可能的一对一错误作为练习不有趣的技术细节被排除在外。

于 2018-02-15T18:39:50.730 回答
1

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

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))))
于 2020-08-10T22:56:49.047 回答