关于斐波那契数列的描述:
斐波那契数列(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大一些。

最后修改:2019 年 04 月 17 日
喜欢就给我点赞吧