快捷導(dǎo)航

C語言中斐波那契數(shù)列的三種實(shí)現(xiàn)方式(遞歸、循環(huán)、矩陣)

更新時(shí)間：2022年01月24日 11:31:16 作者：Bob__yuan

本文主要介紹了C語言中斐波那契數(shù)列的三種實(shí)現(xiàn)方式(遞歸、循環(huán)、矩陣)，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

一、遞歸

一般來說遞歸實(shí)現(xiàn)的代碼都要比循環(huán)要簡(jiǎn)潔，但是效率不高，比如遞歸計(jì)算斐波那契數(shù)列第n個(gè)元素。

long long Fibonacci_Solution1(unsigned int n) {
    // printf("%d ", n);
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}

如果計(jì)算數(shù)列的第4個(gè)位置上（從0開始）的數(shù)（0 1 1 2 3），也就是3，上邊的 printf 輸出應(yīng)該是 4 3 2 1 0 1 2 1 0，這是因?yàn)橛?jì)算 F(4) 要計(jì)算 F(3) 和 F(2)，而計(jì)算 F(3) 的時(shí)候又要計(jì)算 F(2) 和 F(1)，所以會(huì)有很多重復(fù)計(jì)算。用下圖可以更好地說明。

遞歸雖然有簡(jiǎn)潔的優(yōu)點(diǎn)，但它同時(shí)也有顯著地缺點(diǎn)。遞歸由于是函數(shù)調(diào)用自身，而函數(shù)調(diào)用是有空間和時(shí)間的消耗的：每一次函數(shù)調(diào)用，都需要在內(nèi)存棧中分配空間以保存參數(shù)、返回地址及臨時(shí)變量，而且往棧里壓入數(shù)據(jù)和彈出數(shù)據(jù)都需要時(shí)間。

而且除了效率問題之外，遞歸可能引起 調(diào)用棧溢出，因?yàn)樾枰獮槊恳淮魏瘮?shù)調(diào)用在內(nèi)存棧中分配空間，而每個(gè)進(jìn)程的棧的容量是有限的。當(dāng)?shù)俟痰膶蛹?jí)太多，就會(huì)超出棧的容量，導(dǎo)致棧溢出。比如上邊的代碼，輸入40，可以正確返回 12502500，但是輸入 5000 就會(huì)出錯(cuò)。

二、循環(huán)

最常規(guī)的正確做法就是用循環(huán)從小到大計(jì)算。

long long Fibonacci_Solution2(unsigned n) {
    if (n <= 1) return n;
    long long  fib1 = 1, fib0 = 0, fibN = 0;
    for (unsigned int i = 2; i <= n; ++i) {
        fibN = fib1 + fib0;
        fib0 = fib1;
        fib1 = fibN;
    }
    return fibN;
}

或者下邊這種

long long Fibonacci_Solution2(unsigned n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (unsigned int i = 2; i <= n; ++i) {
        b = a + b;
        a = b - a;
    }
    return b;
}

三、矩陣

數(shù)中提到了一種 O(logN) 時(shí)間復(fù)雜度的算法，就是利用數(shù)學(xué)公式計(jì)算。

首先需要知道下邊這個(gè)數(shù)學(xué)公式：

這個(gè)公式用數(shù)學(xué)歸納法可以證明，所以只需要計(jì)算右邊矩陣的 n-1 次方就能得到 f(n)，現(xiàn)在問題就變成了計(jì)算 2x2 矩陣的 n-1 次方，這樣做 n-2 次乘法就可以了，時(shí)間復(fù)雜度還是 O(N)，但是還可以加速，如下式：

所以我們可以看出，想求 n 次方可以求出 n / 2 次方再平方，所以時(shí)間復(fù)雜度可以將為 O(logN)。

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是偶數(shù)
        matrix = MatrixPower(n / 2);
        matrix = MatrixMultiply(matrix, matrix);
    }
    else if (n % 2 == 1) {	// n是奇數(shù)
        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;
}

為了測(cè)試上邊三種方式的代碼的正確性，可以用如下樣例來測(cè)試。

// ====================測(cè)試代碼====================
void Test(int n, int expected) {
    if (Fibonacci_Solution1(n) == expected)
        printf("Test for %d in solution1 passed.\n", n);
    else
        printf("Test for %d in solution1 failed.\n", n);
 
    if (Fibonacci_Solution2(n) == expected)
        printf("Test for %d in solution2 passed.\n", n);
    else
        printf("Test for %d in solution2 failed.\n", n);
 
    if (Fibonacci_Solution3(n) == expected)
        printf("Test for %d in solution3 passed.\n", n);
    else
        printf("Test for %d in solution3 failed.\n", n);
}
 
int main(int argc, char* argv[]) {
    Test(0, 0);
    Test(1, 1);
    Test(2, 1);
    Test(3, 2);
    Test(4, 3);
    Test(5, 5);
    Test(6, 8);
    Test(7, 13);
    Test(8, 21);
    Test(9, 34);
    Test(10, 55);
    Test(40, 102334155);
    return 0;
}

到此這篇關(guān)于C語言中斐波那契數(shù)列的三種實(shí)現(xiàn)方式(遞歸、循環(huán)、矩陣)的文章就介紹到這了,更多相關(guān)C語言斐波那契數(shù)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: