美文网首页数据结构和算法程序员
剑指offer - 斐波拉契数列

剑指offer - 斐波拉契数列

作者: Longshihua | 来源:发表于2019-01-03 09:50 被阅读0次

    求斐波拉契数列的第n项

    写一个函数,输入n,求斐波拉契数列的第n项,斐波拉契数列的定义如下:

    4010043-81a3f4f218d43009.png

    一般解法

    long long Fibonacci(unsigned int n)
    {
        if (n<=0)
            return 0;
        if (n==1)
            return 1;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
    

    这是我们常用的递归函数,但是上述递归的解法存在很严重的效率问题

    分析

    我们以求解f(10)为例来分析递归的求解过程。想求得f(10),需要先求得f(9)和f(8),想求得f(9),需要先求得f(8)和f(7)。。。我们可以用树形结构来表示这种依赖关系,如下图

    2.png

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

    实用解法

    上述代码之所以慢,是因为重复的计算太多,我们只要想办法避免重复计算就好。比如,我们可以把已经得到的数列中间项保存起来,在下次需要的时候我们先查找一下,如果前面已经计算过就不再重复计算了。

    更简单的办法是从下往上计算,首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3)。。。以此类推就可以算出第n项。这种思路的时间复杂度为O(n),实现如下:

    long long Fibonacci(unsigned int n)
    {
        int result[2] = {0,1};
        if (n<2)
            return result[n];
    
        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;
    }
    

    使用矩阵

    先看一个数学公式

    799b1417445527.jpg

    有了这个公式,我们只需要求得矩阵的n-1次方
    \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1}

    就可以得f(n)。现在的问题转换为如何求矩阵
    \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}
    乘方。如果简单地从0开始循环,n次方将需要n次运算,并不比前面的方法要快。

    但我们可以考虑乘方的如下性质:
    a^n=\left\{ \begin{aligned} a^{n/2}.a^{n/2} &&n为偶数\\ a^{(n-1)/2}.a^{(n-1)/2}.a && n为奇数\ \\ \end{aligned} \right.
    由公司可知,要求得n次方,我们先求得n/2次方,再把n/2的结果平方一下即可,这可以利用递归实现

    完整的实现

    #include <cassert>
    
    struct Matrix2By2
    {
        Matrix2By2
        (
            long long m00 = 0, 
            long long m01 = 0, 
            long long m10 = 0, 
            long long m11 = 0
        )
        :m_00(m00), m_01(m01), m_10(m10), m_11(m11) 
        {
        }
    
        long long m_00;
        long long m_01;
        long long m_10;
        long long m_11;
    };
    
    // 矩阵相乘
    Matrix2By2 MatrixMultiply
    (
        const Matrix2By2& matrix1, 
        const Matrix2By2& matrix2
    )
    {
        return Matrix2By2(
            matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
            matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
            matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
            matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
    }
    
    Matrix2By2 MatrixPower(unsigned int n)
    {
        assert(n > 0);
    
        Matrix2By2 matrix;
        if(n == 1)
        {
            matrix = Matrix2By2(1, 1, 1, 0);
        }
        else if(n % 2 == 0) // 偶数
        {
            matrix = MatrixPower(n / 2);
            matrix = MatrixMultiply(matrix, matrix);
        }
        else if(n % 2 == 1) // 奇数
        {
            matrix = MatrixPower((n - 1) / 2);
            matrix = MatrixMultiply(matrix, matrix);
            matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
        }
    
        return matrix;
    }
    
    long long Fibonacci(unsigned int n)
    {
        int result[2] = {0, 1};
        if(n < 2)
            return result[n];
    
        Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
        return PowerNMinus2.m_00;
    }
    

    解法比较

    用不同的方法求解斐波拉契数列的时间效率大不相同,第一种基于递归的解法,虽然直接但时间效率很低,在实际的软件开发中不会用这种方法。

    第二种方法把递归的算法用循环实现,极大地提高了时间效率。

    第三种方法把求斐波那契数列转换成求矩阵的乘方,是一种很有创意的算法。虽然我们可以用O(logn)求的矩阵的n次方,但由于隐含的时间常熟较大,很少会有软件采用这种算法。

    相关问题

    青蛙跳台阶

    一只青蛙一次可以跳上一级台阶,也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    分析

    首先我们考虑最简单的情况。如果只是1级台阶,那显示只有一种条法。如果有2级台阶,那就有两种条法;一种是分两次跳,每次跳1级;另一种就是一次跳2级。

    我们把n级台阶时的跳法看成n的函数f(n)。当n>2时,第一次跳的时候就有两种不同的选择:一是第一次跳一级,此时跳法数目等于后面剩下的n-1级台阶跳法的数目,即f(n-1),二是第一次跳2级,此时跳法数目等于后面剩下的n-2级台阶的跳法数目,即为f(n-2)。因此,n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2),其实就是斐波拉契数列,如下面表达式所示

    20160924125857556.png

    递归实现

    long long Fibonacci(unsigned int n)
    {
        if (n<=0)
            return 0;
        if (n==1)
            return 1;
        if (n==2)  
            return 2;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
    

    循环实现

    long long Fibonacci(unsigned int n)
    {
        if (n<0)
            return 0;
        int result[3] = {0,1,2};
        if (n<3)
            return result[n];
    
        long long fibNMinusOne = 1;
        long long fibNMinusTwo = 2;
        long long fibN = 0;
        for (unsigned int i = 3; i <= n; i++) {
            fibN = fibNMinusOne + fibNMinusTwo;
    
            fibNMinusOne = fibNMinusTwo;
            fibNMinusTwo = fibN;
        }
        return fibN;
    }
    

    矩形覆盖问题

    我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。问用8个2x1的小矩阵无重叠地覆盖一个2x8的大矩阵,共有多少种方法?

    1.jpg

    分析:

    我们将2x8的覆盖方法记为f(8)。用第一个小矩形覆盖大矩形最左边的时候,有两种选择:竖着放置或者横着放置。

    竖着放置的时候,右边还剩下2x7的区域,记为f(7);
    横着放置的时候,左上角放置一个,则对应的左下角必须还有一个小矩阵,则右边还剩下2x6的区域,记为f(6);
    因此,f(8)=f(7)+f(6),可以看出,这仍然是斐波那契数列。

    long long Fibonacci(unsigned int n)
    {
        if (n<=0)
            return 0;
        if (n==1)
            return 1;
        if (n==2)  
            return 2;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
    

    参考

    《剑指offer》

    相关文章

      网友评论

        本文标题:剑指offer - 斐波拉契数列

        本文链接:https://www.haomeiwen.com/subject/tyldfqtx.html