呼吁第n个斐波纳契数数 [英] Number of calls for nth Fibonacci number

问题描述

考虑以下code片断：

Consider the following code snippet:

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

由于 FIB 从主被称为以N为10,35,67，......（说），一共有多少电话 都是为了 FIB ？

Given that fib is called from main with N as 10,35,67,... (say), how many total calls are made to fib?

有没有针对此问题的任何关系？

Is there any relation for this problem?

PS：这是一个理论问题和不应该被执行

PS: This is a theoretical question and not supposed to be executed.

编辑：

我所知道的其他方法来斐波那契数列的速度更快的计算。

I am aware of other methods for the faster computation of Fibonacci series.

我想计算的时候FIB数量的解决方案被调用FIB（40），FIB（50），...没有编译器的帮助和考试情况，你都应该回答40问题与此类似的在规定的时间（约30薄荷糖）。

I want a solution for computing number of times fib is invoked for fib(40),fib(50) ,.. without the aid of compiler and in exam condition where you are supposed to answer 40 question similar to this one in a stipulated of time ( about 30 mints).

谢谢

推荐答案

让 F（N）的是做计算 FIB（N）的呼叫数量。

• 如果的 N'LT; 2 的那么的 F（N）= 1 的
• 另外， F（N）= 1 + F（N - 1）+ F（N - 2）。的

• If n < 2 then f(n) = 1.
• Otherwise, f(n) = 1 + f(n - 1) + f(n - 2).

因此​​， F 的是至少的 O（FIB（N））的。事实上， F（N）的是 2 * FIB（N） - 1 的。我们表明，该通过感应：

So, f is at least O(fib(n)). In fact, f(n) is 2 * fib(n) - 1. We show this by induction:

• 在基本情况下（ N'2 的，就是 N = 0 或 N = 1 的）：
  • F（N）= 1 = 2 * 1 - 1 = 2 * FIB（N） - 1 的
  • Base cases (n < 2, that is, n = 0 or n = 1):
    • f(n) = 1 = 2 * 1 - 1 = 2 * fib(n) - 1.
    • 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 + 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个斐波纳契数数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！