纵有疾风起
人生不言弃

剑指Offer面试题:8.斐波那契数列


一、题目:斐波那契数列

题目:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列的定义如下: 

剑指Offer面试题:8.斐波那契数列插图

二、效率很低的解法

  很多C/C++/C#/Java语言教科书在讲述递归函数的时候,大多都会用Fibonacci作为例子,因此我们会对这种解法烂熟于心:

    public static long FibonacciRecursively(uint n)    {        if (n <= 0)        {            return 0;        }        if (n == 1)        {            return 1;        }        return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);    }

  上述递归的解法有很严重的效率问题,通过求解第10项的调用过程图来分析:

剑指Offer面试题:8.斐波那契数列插图(1)

  从上图中不难发现:在这棵树中有很多结点是重复的,而且重复的结点数会随着n的增大而急剧增加,这意味计算量会随着n的增大而急剧增大。事实上,用递归方法计算的时间复杂度是以n的指数的方式递增的

三、实用循环的解法

  改进的方法并不复杂。上述递归代码之所以慢是因为重复的计算太多,我们只要想办法避免重复计算就行了。这里的办法是从下往上计算,首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3)……依此类推就可以算出第n项了。很容易理解,这种思路的时间复杂度是O(n)

    public static long FibonacciIteratively(uint n)    {        int[] result = { 0, 1 };        if (n < 2)        {            return result[n];        }        long fibNMinusOne = 1;        long fibNMinusTwo = 0;        long fibN = 0;        for (uint i = 2; i <= n; i++)        {            fibN = fibNMinusOne + fibNMinusTwo;            fibNMinusTwo = fibNMinusOne;            fibNMinusOne = fibN;        }        return fibN;    }

四、单元测试

  (1)单元测试用例

    [TestMethod]    public void FibonacciTest1()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(0),0);    }    [TestMethod]    public void FibonacciTest2()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(1), 1);    }    [TestMethod]    public void FibonacciTest3()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(2), 1);    }    [TestMethod]    public void FibonacciTest4()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(3), 2);    }    [TestMethod]    public void FibonacciTest5()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(4), 3);    }    [TestMethod]    public void FibonacciTest6()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(5), 5);    }    [TestMethod]    public void FibonacciTest7()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(6), 8);    }    [TestMethod]    public void FibonacciTest8()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(7), 13);    }    [TestMethod]    public void FibonacciTest9()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(8), 21);    }    [TestMethod]    public void FibonacciTest10()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(9), 34);    }    [TestMethod]    public void FibonacciTest11()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(10), 55);    }    [TestMethod]    public void FibonacciTest12()    {        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(40), 102334155);    }

  (2)单元测试结果

  ①测试通过结果

剑指Offer面试题:8.斐波那契数列插图(2)

  ②代码覆盖率

剑指Offer面试题:8.斐波那契数列插图(3)

 

文章转载于:https://www.cnblogs.com/edisonchou/p/4752052.html

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » 剑指Offer面试题:8.斐波那契数列

分享到: 生成海报
avatar

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活