学步园

这个数列从第三项开始，每一项都等于前两项之和。
解法一：可以使用递归求解，代码如下：

#include<iostream>
using namespace std;
long long Fib(unsigned int);
int main()
{
    for(int i=1;i<20;i++)
        cout<<Fib(i)<<endl;
    cout<<endl;
    return 0;
}
long long Fib(unsigned int n)
{
    if(n==1)
        return 0;
    if(n==2)
        return 1;
    else
        return Fib(n-1)+Fib(n-2);
}

递归问题有着严重的效率问题 ，随着n的增大，递归方法的复杂度是以n的指数的方式递增的。
解法二：
更简单的方法是从底向上计算，即先求出Fib(1),Fib(2)，然后求出Fib(3).....以此类推就可以计算出第n项了，这种方法的时间复杂度是O(n).
代码如下：

#include<iostream>
using namespace std;
long long Fibonacci(unsigned int);
int main()
{
    cout<<Fibonacci(1)<<endl;
    cout<<Fibonacci(10)<<endl;
    return 0;
}
long long Fibonacci(unsigned int n)
{
    if(n==1)
        return 0;
    if(n==2)
        return 1;
    long long FibNMinusOne =0;
    long long FibNMinusTwo=1;
    long long FibN=0;
    for(unsigned int i=2;i<n;i++)
    {
        FibN= FibNMinusOne + FibNMinusTwo;
        FibNMinusOne =FibNMinusTwo;
        FibNMinusTwo =FibN;
    }
    return FibN;
}

运行结果：


Reference《算法分析与设计基础》潘彦译
《计算机算法与分析》 王晓东
《名企面试官精讲典型编程题》 何海涛