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

一、题目:斐波那契数列

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

二、效率很低的解法

  很多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项的调用过程图来分析:

  从上图中不难发现:在这棵树中有很多结点是重复的,而且重复的结点数会随着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)单元测试结果

  ①测试通过结果

  ②代码覆盖率

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

技术 | Python从零开始系列连载(二十四)

为了解答大家学习Python时遇到各种常见问题,小灯塔特地整理了一系列从零开始的入门到熟练的系列连载,每周五准时推出,欢迎大家学积极学习转载~

1012
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

1802
来自专栏mySoul

设计模式-UML关系基础

1155
来自专栏ml

HDUOJ-----(1251)统计难题

统计难题 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Jav...

3639
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第五章 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦了...

3655
来自专栏闵开慧

曾经做过的40道程序设计课后习题总结(一)

曾经做过的40道程序设计课后习题总结(一) 课后习题目录 1 斐波那契数列 2 判断素数 3 水仙花数 4 分解质因数 5 杨辉三角 6 学习成绩查询...

3418
来自专栏来自地球男人的部落格

[LeetCode] 119. Pascal's Triangle II

【原题】 Given an index k, return the kth row of the Pascal’s triangle. For exampl...

2076
来自专栏李智的专栏

pandas数据清洗,排序,索引设置,数据选取

df.isnull() df的空值为True df.notnull() df的非空值为True

1342
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第11章 时间序列11.1 日期和时间数据类型及工具11.2 时间序列基础11.3 日期的范围、频率以及移动11.4 时区处理时区本地化和转换11.5 时期及其

时间序列(time series)数据是一种重要的结构化数据形式,应用于多个领域,包括金融学、经济学、生态学、神经科学、物理学等。在多个时间点观察或测量到的任何...

6646
来自专栏Leetcode名企之路

【Leetcode】60. 第k个排列

给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1:

2922

扫码关注云+社区

领取腾讯云代金券