查找递归程序的加法步骤数

Question

我正在进行一个小测验，似乎很难理解一个特别的问题。

1. 斐波那契序列1,1,2,3，.可以从前两个(第0和第1)开始迭代生成，并通过添加前两个来生成每个后续的。因此，如果我们从前两个开始，n≥2的第n个斐波那契数可以由n个−1加法生成。特别是，我们需要6个加法来生成第7斐波那契数。但是，生成第七个斐波那契数的递归程序需要：

(a) 20项增加(c) 5项增列(b) 13项增列(d) 18项

答: a)增加20项

我不太明白他们怎么会增加20个。有没有一种快速的方法可以找到斐波纳契序列的递归程序的加法？我尝试通过c++中的递归代码进行跟踪，我在网上找到了这些代码，但我不确定哪些是添加步骤。

我只是在找一个关于如何得到答案的解释。我很感谢你的帮助。

Answer 1

用n个数字所需的加法数制作一个小表格.当你计算f(x)为f(x-1) + f(x-2)时，你需要加法来计算f(x-1)和f(x-2)的加法，以及这两个数之和的加法。

n     additions
0     0
1     0
2     1 (= n(0) + n(1) + 1)
3     2 (= n(1) + n(2) + 1)
4     4 (= n(2) + n(3) + 1)
5     7 (= n(3) + n(4) + 1)
6    12 (= n(4) + n(5) + 1)
7    20 (= n(5) + n(6) + 1)

Answer 2

简单的递归公式如下所示：

F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2)

所以有一种方法就是做替换.

F(7) = F(6) + F(5)
     = F(5) + F(4) + F(4) + F(3)
     = F(4) + F(3) + F(3) + F(2) + F(3) + F(2) + F(2) + F(1)
     = F(3) + F(2) + F(2) + F(1) + F(2) + F(1) + F(1) + F(0) + F(2) + F(1) + F(1) + F(0) + 1
     = F(2) + F(1) + F(1) + F(0) + F(1) + F(0) + 1 + F(1) + F(0) + 1 + 1 + 1 + F(1) + F(0) + 1 + 1 + 1 + 1
     = F(1) + F(0) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
     = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1  

...and添加+符号。

另外，请注意，递归公式的每一步都以F( 1 )和或F(0)结尾，每一步都有值1。因此，对于任何n> 1，(在展开公式之后)，您将得到足够的1's之和，从而生成F(n)。因此，朴素递归公式总是需要F(n)-1加法(因此，在F(7)=21，即20加法的情况下)。

Answer 3

您可以用一个封闭的公式快速计算这一点，该公式要求所有n>0的当前和以前的斐波那契数。

S(n) = F(n-1) + F(n) -1

其中Sn是第n项的加法数，F(n)和F(n-1)是nth和nth-1 Fibonacci数。

例如：

S(10) = F(9) + F(10) -1

S(10) = 34 + 55 - 1

S(10) = 88