关于斐波那契数列的描述：
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

一、面试题

求斐波那契数列的第n项：写一个函数，输入n，输出斐波那契数列的第n项。

二、解法一

求斐波那契数列最简单的解法就是用递归，大部分书籍上介绍递归的时候都会用斐波纳契数列做例子，递归很容易写：

long long Fibonacci_Solution1(unsigned int n)
{
    if(n <= 0)
        return 0;

    if(n == 1)
        return 1;

    return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}

这个解法并不是最优的，因为中间充斥了很多重复的运算，应该还不足以应付面试。例如计算f(10)的过程中：

f(6)/f(7)/f(8)都被计算了多次，当数据越大时，重复计算的次数也越来越多，因此并不是最优的解法。

三、解法二

上面的递归之所以慢，是因为重复的计算太多，我们可以考虑从如何减少重复计算下手。例如可以选择从2开始，保存前两位的值，依次向后计算：

long long Fibonacci_Solution2(unsigned n)
{
    int result[2] = {0, 1};
    if(n < 2)
        return result[n];

    long long  fibNMinusOne = 1;
    long long  fibNMinusTwo = 0;
    long long  fibN = 0;
    for(unsigned int i = 2; i <= n; ++ i)
    {
        fibN = fibNMinusOne + fibNMinusTwo;

        fibNMinusTwo = fibNMinusOne;
        fibNMinusOne = fibN;
    }

     return fibN;
}

注意事项：传参的n的类型为unsigned int，保存值以及返回值的数据类型是long long，避免int溢出。

ps：虽然long long也会溢出，至少比int大一些。