C++中實現fibonacci數列的幾種方法是哪些呢

小編今天帶大家了解C++中實現fibonacci數列的幾種方法是哪些呢，文中知識點介紹的非常詳細。覺得有幫助的朋友可以跟著小編一起瀏覽文章的內容，希望能夠幫助更多想解決這個問題的朋友找到問題的答案，下面跟著小編一起深入學習“C++中實現fibonacci數列的幾種方法是哪些呢”的知識吧。

前言

fibonacci數列的實現主要有三種方法：遞歸、循環與矩陣。這里主要學習了如何在C++中實現這三種方法以及分析它們各自的時間復雜度。

一、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.遞歸的特點

• 遞歸：函數自己調用自己

• 遞歸的"缺陷"：遞歸到一定程度，會發生"棧溢出"

• 遞歸的"時間復雜度"：遞歸總次數*每次遞歸的次數

• 遞歸的"空間復雜度"：遞歸的深度*每次遞歸空間的大?。ㄗ⒁猓?quot;每次遞歸空間的大小"是個常數，可以基本忽略不計）

• 遞歸的"深度"：樹的高度（遞歸的過程是一個"二叉樹"）

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.時間復雜度

• 時間復雜度：O(N)

• 空間復雜度：O(1)（創建了四個對象，是常數，所以可忽略不計）

四、矩陣實現

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）。

感謝大家的閱讀，以上就是“C++中實現fibonacci數列的幾種方法是哪些呢”的全部內容了，學會的朋友趕緊操作起來吧。相信億速云小編一定會給大家帶來更優質的文章。謝謝大家對億速云網站的支持！