亲宝软件园·资讯

展开

C++ fibonacci数列

关关在干嘛 人气:0

前言

fibonacci数列的实现主要有三种方法:递归、循环与矩阵。这里主要学习了如何在C++中实现这三种方法以及分析它们各自的时间复杂度。

本文参考文章如下:https:

一、fibonacci数列是什么?

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)

二、递归实现

1.递归的特点

2.C++实现

int main(){
    int n;
    long long sum;  
    
    scanf("%d",&n);
    sum =fb(n);  
    printf("%lld\n",sum);
    
    return 0;
}
 
long long fb(int n){
    if(n<1){
        return 0;
        
    }else if(n==1||n==2){
        return 1;
    }
    return (fb(n-1)+fb(n-2));
}

3.时间复杂度

二叉树的高度是 n - 1,一个高度为k的二叉树最多可以有 2^k - 1个叶子节点,也就是递归过程函数调用的次数,所以时间复杂度为 O(2^n),而空间复杂度就是树的高度 O(n)。

三、循环实现

1.C++实现

long long Fib(long long N)
{
    long long first = 1;
    long long second = 1;
    long long ret = 0;
    for (int i = 3; i <=N; ++i)
    {
        ret = first + second;
        first = second;
        second = ret;
    }
    return second;
}
int main()
{
    long long num = 0;
    num=Fib(10);
    printf("循环:%d\n", num);
    system("pause");
    return 0;
}

2.时间复杂度

四、矩阵实现

1.理论推导

斐波那契数列的递推公式是:f(n)=f(n-1)+f(n-2);

 在线性代数中,类似于斐波那契数列这种递推式称为二阶递推式。我们可以用f(n)=af(n-1)+bf(n-2)将二阶递推式一般化。只要符合这种二阶递推式的算法,都可以将算法的时间复杂度降为O(logN)。当然,三阶,四阶....都可以,只要得到递推公式的n阶矩阵即可。如下:

     f(n)=af(n-1)+bf(n-2)+......

     (f(n),f(n-1))=(f(n-1),f(n-2))*matrix;(matrix是一个矩阵,几阶递推式就是几阶的矩阵,在这里是二阶的矩阵,斐波那契数列属于二阶)

……………………①

………………②

于是只要求得即可。

而类似求还可以简化(快速幂)

例如:

10^68,我们通常是10*10乘上68次,这样时间效率为O(N),我们要用O(logN)方法算:

     68的二进制序列为:1000100

     10^68=10^64*10^4,也就是取出68二进制序列为1的位,其他忽略。这样我们只算了7次(二进制序列的长度)就可以算出10^68,效率就达到了O(logN)。(最优化算法的关键所在)

所以时间复杂度可以达到最优化O(logN)。

2.C++实现

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, m_01, m_10, 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) {    // n是偶数
        matrix = MatrixPower(n / 2);
        matrix = MatrixMultiply(matrix, matrix);
    }
    else if (n % 2 == 1) {    // n是奇数
        matrix = MatrixPower((n - 1) / 2);
        matrix = MatrixMultiply(matrix, matrix);
        matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
    }
    return matrix;
}
 
long long Fibonacci_Solution3(unsigned int n) {
    if (n <= 1) return n;
    Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
    return PowerNMinus2.m_00;
}

3.时间复杂度

O(logN)。

加载全部内容

相关教程
猜你喜欢
用户评论