斐波那契数列

斐波那契数列

四月 14, 2019

题目描述


    大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。


通过递归

    首先，很容易就想到了递推公式。因此我们马上就能想到使用递归方法，代码如下：

class Solution
{
public:
    int Fibonacci(int n)
    {
        if(n <= 1)
        {
            return n;
        }
        else
        {
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }
};

    但实际上递归方法的时间复杂度是以n的指数方式增长的。

递归展开-迭代方法

    因此我们只能用最普通的方法，将递推公式进行展开。

class Solution
{

public:
    int Fibonacci(int n)
    {
        if(n <= 1)
        {
            return n;
        }
        long one = 0;
        long two = 1;
        long res = 0;

        for(int i = 2; i <= n; i++)
        {
            res = one + two;

            one = two;
            two = res;
        }

        return res;
    }
};

    但这还不是最快的方法，下面介绍一种时间复杂度是的方法。

$O(logn)$求Fibonacci数列

    在介绍此方法前，先介绍一个数学公式：

    有了此公式，求就只要求出矩阵的n-1次方，因为矩阵的n-1次方的第一行第一列就是f(n)。这个公式使用数学归纳法不难得出。那么问题又来了，从0开始到n-1，实际上还是需要n次运算，并不比上面的方法快。但是我们可以利用同底数幂法则：

或

    要求n次方，现求出次方后，再平方即可。
    用这种方式实现时，首先要定义一个2*2的矩阵。并定义好矩阵的乘法以及幂运算。

    接下来再介绍一种推理公式：

    当n=2k和n=2k-1推理公式以及代码如下：

class Solution {

    
public:
    int post;//存Fibonacci(n-1)
    int pre;//存Fibonacci(n)
    int temp;
    
    int Fibonacci(int n) {
        if(n <= 2){
            if(n == 0)
                return 0;
            pre = 1;
            post = 1;
            return post;
        }
        /*
        (1):
        a(n) = a(n-1) + a(n-2)
             = a(n-2) + a(n-3) + a(n-2)
             = 2 * a(n-2) + a(n-3)
             = 3 * a(n-3) + 2 * a(n-4)
             = a(k) * a(n - k + 1) + a(k-1) * a(n-k)
        */
        /*
        奇数情况：
        令n=2k-1;
        由(1)式得：
        a(2k-1) = a(k) * a(k) + a(k-1) * a(k-1)
                = a(k)^2 + a(k-1)^2
        */
        /*
        偶数情况：
        令n=2k;
        由(1)式得：
        a(2k) = a(k) * a(k+1) + a(k-1) * a(k)
                = a(k)^2 + 2 * a(k) * a(k-1)
        */
        
        //n为奇数，则做减一操作，函数返回时
        //pre: f(n) = f(n-1) + f(n-2)
        //post: f(n-1) = f(n) - f(n-2)
        
        if(n % 2 == 1){
            Fibonacci(n-1);
            pre = pre + post;
            post = pre - post;
            return pre;
        }
        
        //n为偶数，一直除以2
        
        Fibonacci(n/2);
        temp = pre;
        pre = pre * pre + 2 * pre * post;
        post = temp * temp + post * post;
        return pre;
        
        
        
    }
};
  1. 1. 题目描述
  2. 2. 通过递归
  3. 3. 递归展开-迭代方法
  4. 4. $O(logn)$求Fibonacci数列