C語言深入探究斐波那契數(shù)列

更新時間：2022年05月11日 11:35:59 作者：GG_Bond18

斐波那契數(shù)一般指斐波那契數(shù)列。斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，因數(shù)學家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱為兔子數(shù)列

一、遞歸思想

遞歸的思想是把一個大型復雜問題層層轉(zhuǎn)化為一個與原問題規(guī)模更小的問題，問題被拆解成子問題后，遞歸調(diào)用繼續(xù)進行，直到子問題無需進一步遞歸就可以解決的地步為止。

#include<stdio.h>
int fib(int n)
{
    return n > 2 ? n : fib(n - 1) + fib(n - 2);
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", fib(n));
    return 0;
}

其時間復雜度為O(2^N),由于其時間復雜度太高，在實際應用中用武之地并沒有想象的那么多，要是真寫個這種程序，老板應該是不容下你了。

二、空間換時間

動態(tài)開辟空間將計算出的數(shù)據(jù)記錄下來，避免重復計算，使用空間換時間。

時間復雜度O(n),空間復雜度O(n)。

#include<stdio.h>
#include<stdlib.h>
long long fib(int n)
{
    long long* p = (long long*)malloc(sizeof(long long) * (n+1));
    p[0] = 0;
    p[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        p[i] = p[i - 1] + p[i - 2];
    }
    long long temp = p[n];
    free(p);
    p = NULL;
    return temp;
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%lld\n", fib(n));
    return 0;
}

這里使用動態(tài)開辟空間而不用數(shù)組，因為數(shù)組的大小有限制。

其缺點依然十分明顯，其空間復雜度較高，開辟堆區(qū)內(nèi)存，若管理不當，甚至可能造成內(nèi)存泄漏。(避免因未釋放堆區(qū)而造成內(nèi)存泄漏的小技巧：(7條消息) C++11智能指針的解析_GG_Bond18的博客-CSDN博客

https://blog.csdn.net/GG_Bruse/article/details/124136480)

三、動態(tài)規(guī)劃

本方法是在方法二的基礎上節(jié)省空間。利用滾動數(shù)組思想，將空間復雜度由O(n)優(yōu)化為O(1)。時間復雜度依然為O(n)。

#include<stdio.h>
long long fib(int n)
{
    if (n < 2)
    {
        return n;
    }
    long long left = 0, right = 1, ret = 1;
    for (int i = 2; i < n; ++i)
    {
        left = right;
        right = ret;
        ret = left + right;
    }
    return ret;
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%lld\n", fib(n));
    return 0;
}

基本掌握這個方法就可以了。

四、通項公式

#include<stdio.h>
#include<math.h>
int fib(int n)
{
    double sqrt5 = sqrt(5);
    double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);
    return round(fibN / sqrt5);
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", fib(n));
    return 0;
}

代碼中使用的pow函數(shù)的時空復雜度與 CPU 支持的指令集相關(guān)，該文章不深入分析。

五、矩陣快速冪

#include<stdio.h>
struct Matrix
{
    int mat[2][2];
};
struct Matrix matrixMultiply(struct Matrix* a, struct Matrix* b)
{
    struct Matrix c;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c.mat[i][j] = (*a).mat[i][0] * (*b).mat[0][j] + (*a).mat[i][1] * (*b).mat[1][j];
        }
    }
    return c;
}
struct Matrix matrixPow(struct Matrix a, int n)
{
    struct Matrix ret;
    ret.mat[0][0] = ret.mat[1][1] = 1;
    ret.mat[0][1] = ret.mat[1][0] = 0;
    while (n > 0) {
        if (n & 1) {
            ret = matrixMultiply(&ret, &a);
        }
        n >>= 1;
        a = matrixMultiply(&a, &a);
    }
    return ret;
}
int fib(int n)
{
    if (n < 2)
    {
        return n;
    }
    struct Matrix q;
    q.mat[0][0] = q.mat[0][1] = q.mat[1][0] = 1;
    q.mat[1][1] = 0;
    struct Matrix res = matrixPow(q, n - 1);
    return res.mat[0][0];
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", fib(n));
    return 0;
}

時間復雜度為O(logn),空間復雜度為O(1)。