第n个Fibonacci数的调用次数
请考虑以下代码段：
int fib(int N) { if(N<2) return 1; return (fib(N-1) + fib(N-2)); } 假设从主要调用fib ，N为10,35,67，……（比如说），对fib进行了多少次调用？
这个问题有什么关系吗？
PS：这是一个理论问题，不应该被执行。
编辑：
我知道其他方法可以更快地计算Fibonacci系列。
我想要一个解决方案来计算fib的调用次数fib（40），fib（50），…没有编译器的帮助，并且在考试条件下你应该回答40个类似于这个规定的问题时间（约30分钟）。
谢谢，
设f（n）为计算fib(n)的调用次数。
- 如果n <2，则f（n）= 1 。
- 否则， f（n）= 1 + f（n-1）+ f（n-2） 。
因此， f至少为O（fib（n）） 。 实际上， f（n）是2 * fib（n）-1 。 我们通过归纳显示：
- 基本情况（ n <2 ，即n = 0或n = 1 ）：
- f（n）= 1 = 2 * 1 – 1 = 2 * fib（n）-1 。
- 诱导步骤（ n> = 2 ）：
- f（n + 1）= f（n）+ f（n-1）+ 1
- f（n + 1）= 2 * fib（n）-1 + 2 * fib（n-1）-1 + 1
- f（n + 1）= 2 * fib（n + 1）-1
存在计算任何斐波纳契项的有效方法 。 因此f（n）也是如此 。
这个问题有什么关系吗？
第n个斐波纳契数有一个紧密forms的等式： http ： //en.wikipedia.org/wiki/Fibonacci_number#Closed_form_expression
在您发布的伪代码中，调用次数满足递归关系
x(n) = x(n-1) + x(n-2) +1 # for n>=2 x(1) = 1 x(0) = 1
这与Fibonacci递归关系几乎相同。 通过感应certificate可以显示由fib（n）产生的对fib的调用数等于2 * fib（n）-1，对于n> = 0。
当然，可以通过使用闭合表单表达式或通过添加代码来记忆先前计算的值来加速计算。
如上所述，您需要求解以下重复方程：K（n）= K（n-1）+ K（n-2）+1
让我们把它写成n-1：K（n-1）= K（n-2）+ K（n-3）+1
现在，从第一个中减去第二个：K（n）-K（n-1）= K（n-1） – K（n-3），
要么
K（n）-2 * K（n-1）+ K（n-3）= 0。
各个特征方程将是：x ^ 3 – 2 * x ^ 2 + 1 = 0。
它有以下根：1，（1 + sqrt（5））/ 2，（1-sqrt（5））/ 2
因此，对于任何实数A，B，C，以下函数K（n）= A *（1）^ n + B *（（1 + sqrt（5））/ 2）^ n + C *（（1-sqrt（ 5））/ 2）^ N
将是你的等式的解决方案。
要找到A，B，C，您需要定义几个初始值K（0），K（1），K（2）并求解方程组。
phi是一个常数
position = ceil(log((n - 0.5)*sqrt(5))/log(phi));
n是斐波纳契数…位置将给出哪个斐波纳契数是n
例如给定13，位置将是7 – 0 1 1 2 3 5 8 13
使用此位置只计算位置-1处的斐波纳契数或您想要的任何位置相对于给定的斐波纳契数。
Previous Fibo Num = floor((pow(phi,position-1)/sqrt(5))+0.5);
floor((pow(phi, position)/sqrt(5))+0.5) – 是计算Nth fibonacci num的标准公式（注意 – 这不是近似值）
我刚刚反转这个公式来计算位置并使用位置-1来计算之前的斐波纳契数。
Ref – http://itpian.com/Coding/20951-Given-the-Nth-fib-no-and-find-the–N-1-th-fib-number-without-calculating-from-the-beginning ———。ASPX
这是使用递归关系求解的经典问题。
具体而言，斐波那契问题具有以下参数：
f(0) = 1 f(1) = 1 f(n) = f(n-1) + f(n-2)
一旦你掌握了解决重现的问题，你就可以毫无问题地达到解决方案（这与fib(n)完全相同）。
有趣的问题，我不能给你一个公式，但我写了一个Ruby程序来做它，它适用于我在纸上想出的数字，它应该适用于任何。
#!/usr/bin/ruby #find out how many times fib() would need to be called def howmany(n) a = [ ] a.push n-1 a.push n-2 while a.select{|n| n > 2}.length > 0 a.map! do |n| n > 2 ? [n-1,n-2] : n end a.flatten! end a.length end
。
>> howmany(10) => 55
它很慢..我现在正在弄清楚35，我会在它完成时进行编辑。
编辑：
>> howmany(35) => 9227465