c++ - 第n个斐波那契数的调用次数

考虑以下代码片段:

int fib(int N)
{
   if(N<2) return 1;
   return (fib(N-1) + fib(N-2));
}

给定fib是从main调用的，N为10、35、67，...(例如)，总共有多少个调用
被制成fib吗？

这个问题有关系吗？

PS:这是一个理论问题，不应执行。

编辑:

我知道可以更快地计算斐波那契数列的其他方法。

我想要一种计算fib(fib(40)，fib(50))调用次数的解决方案，而无需编译器的帮助，并且在考试条件下，您应按照规定的条件回答类似于此问题的40个问题时间(大约30分钟)。

谢谢，

最佳答案

令f(n)为计算fib(n)的调用次数。

如果n

否则，f(n)= 1 + f(n-1)+ f(n-2)。

因此，f至少为O(fib(n))。实际上，f(n)是2 * fib(n)-1。

基本案例(n

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

存在efficient ways来计算任何斐波纳契项。因此，f(n)也是一样。

关于c++ - 第n个斐波那契数的调用次数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1738923/