求斐波那契数列的第n项值——9

    写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下:

         0            n = 0     

   F(n) =  1            n = 1

         F(n-1)+F(n-2)    n > 1

也就是斐波那契数列为{0,1,1,2,3,5,8,13,21，......F(n-1)+F(n-2)}；

    首先可以想到，因为要求第n个斐波那契数，就需要知道第n-1和第n-2个斐波那契数，而求第n-1个斐波那契数就需要知道第n-2个和第n-3个斐波那契数，第n-2个斐波那契数就需要知道第n-3和第n-4个斐波那契数......这样的话，可以用递归来实现：

#include <iostream>
using namespace std;

long long Fib(size_t n)
{
    if(n < 2)
        return n;
    else
        return Fib(n-1)+Fib(n-2);
}

int main()
{
    size_t n = 18; 
    long long ret = Fib(n);
    cout<<"Fibonacci number of "<<n<<" is: "<<ret<<endl;
    return 0;
}

运行程序可得结果：

可以看到第18个斐波那契数为2584，这种情况下是没什么问题的，但如果将n的值再设大一点的话，比如38，或者48、58，就会发现半天运算不出来结果，这是因为递归会有栈的开销，而一个稍微大点的n就会连续压十几个甚至好几十个栈，这样的话，系统的运算效率就大大降低了，因此，用递归来计算斐波那契数并不是最高效的解法。

    递归是不断地压栈释放栈，在每一块开辟出来的栈中保存有n个斐波那契数，那么，除了用递归，也可以用数组来依次存储从0到n个斐波那契数，用循环来代替栈的开销，代码可如下：

long long Fib(size_t n)
{
    if(n < 2)     //当n小于2的时候就可以直接返回效率高，就不必再开辟释放空间了
        return n;

    long long *p = new long long[n+1];//因为n相当于下标，存在第0个斐波那契数，因此要开辟n+1的大小
    p[0] = 0;
    p[1] = 1;

    for(size_t i = 2; i <= n; ++i)//循环控制条件下标为n的值才是要返回的值
    {
        p[i] = p[i-1] + p[i-2];
    }
    long long ret = p[n];
    delete[] p;//记得释放空间，否则会有内存泄露
    return ret;
}

运行上面的程序，会发现无论n为多大结果很快就能够得出来，这样的运行效率是比递归压栈要高的多的；

    可是，上面的程序还是存在问题，因为如果n的值比较大的话，开辟的空间也会很大，但是我们会发现，要求第n个斐波那契数，只需要知道它前面的两个数然后相加起来就可以了，也就是说，明明只需要三个数据的空间用来存放数据就好了却要开辟出很大的一块空间来将n前面所有的数据都给存放起来，因此，上面的程序虽然比递归压栈效率要高，但是却比较浪费存储空间；上面的代码还是可以优化为如下的：

long long Fib(size_t n)
{
    if(n < 2)
        return n;

    long long f0, f1, f2; //定义三个变量
    f0 = 0;
    f1 = 1;

    for(size_t i = 2; i <= n; ++i)
    {   
        f2 = f0 + f1; //每一次都用三个变量来回交换，因为要求n只需要知道前面两个数就可以了
        f0 = f1; 
        f1 = f2; 
    }   
    return f2; 
}

《完》