不知道如何解决sic颗粒行使1.11

StackOverflow https://stackoverflow.com/questions/2365993

题

1.11锻炼:

一个功能 f 是定义规则， f(n) = n 如果 n < 3 和 f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) 如果 n > 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))))

阅读后，我明白的代码，以及它如何工作。但我不明白的是该进程需要得到从递归的定义的功能。我没有得到代码如何可以形成在别人的头上。

你能解释的思想过程中需要达成解决办法？

有帮助吗？

解决方案

您需要捕捉状态在某些蓄电池和在每次迭代更新的状态。

如果您在命令式语言中有经验，想象写一个while循环，循环的每次迭代中跟踪变量的信息。你需要什么因素？你将如何对其进行更新？这正是你必须做的，使迭代（尾递归）集方案调用的东西。

在换句话说，它可能有助于启动的这一思想作为一个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

这仍然是从计划迭代版本有点不同，但我希望你现在可以看到的思维过程。

其他提示

我觉得你问一个如何可能发现算法自然，一个“设计模式”之外。

这是有帮助的我看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，I可以通过计算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)

由于我们将重新使用它们，让给他们的名称的，B，C。

：与步骤我们对，并且穿行f的计算（5）下标 
  Step 1:    f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a1 + 2b1 +3c1

，其中

一个<子> 1 = F（2）= 2，

B'的子> 1 = F（1）= 1，

C <子> 1 = 0

由于f（N）= N对于n <3。

因此：

F（3）=α<子> 1 + 2B <子> 1 + 3C <子> 1 = 4 

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

所以：

一个<子> 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 

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

所以：

一个<子> 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

在前面的计算

在整个上面的计算，我们捕获状态，并将其传递到下一个步骤， particularily：

一个<子>步骤 =步骤的结果 - 1

B'子>步骤 = A <子>步骤 - 1

C <子>步骤 = B <子>步骤-1

在我看到这一点，那么未来与迭代版本是直截了当的。

由于您链接到文章描述了很多关于解决方案，我会尽量只给出补充信息。

您正试图在这里定义方案一尾递归函数，给定一个（非尾）递归定义。

递归的基础案例（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），和递减计数

如果这仍然不能解决问题，请试着问一个更具体的问题 - 这真的很难回答，当你写“我不明白”已经给出一个相对完整的解释

我要在这在一个稍微不同的方法，其他的答案在这里，集中于如何编码式可以作背后的思维过程的一个算法，这样更容易理解。

的麻烦 比尔的方法, 引你的问题是，它不清楚是什么 意思 是达状态变量， a, b, ， c.他们的名字传达的信息不，比尔的后并没有描述任何固定或其他规则，他们服从。我发现更容易这两个制定和了解的迭代的算法，如果状态变量服从一些记录的规则描述它们之间的关系。

铭记这一点，考虑这个备选案文完全相同的算法，这不同于法案是只有在具有更有意义的变量名称 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, 我们正在这样做。
  

一个函数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

相信与否，有一度这样的语言。写在另一种语言下来仅仅是一个语法的问题。顺便说一下，定义为你（MIS）引用它有一个错误，这是现在非常明显和清晰。

  

撰写程序，其计算f通过迭代过程的手段。

迭代意味着去向前 （有的你的解释），而不是递归的去的向后的首先！

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'          a' = a+2b+3c, b' = a, c' = 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

这是已经完全像你问的代码，最多的语法。

计数达的名词的更自然在这里，下面我们的“前进”的范例，但倒计时的 0 的为您引用的代码确实是当然完全等效。

在极端情况和可能的断接一个错误被排除作为锻炼非有趣的技术性。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top