C語言深入探究斐波那契數(shù)列
本文章參考leetcode斐波那契數(shù)官方題解
斐波那契的邊界條件是 F(0)=0 和 F(1)=1。當(dāng) n>1 時，每一項的和都等于前兩項的和，因此有如下遞推關(guān)系：F(n)=F(n-1)+F(n-2)
一、遞歸思想
遞歸的思想是把一個大型復(fù)雜問題層層轉(zhuǎn)化為一個與原問題規(guī)模更小的問題，問題被拆解成子問題后，遞歸調(diào)用繼續(xù)進(jìn)行，直到子問題無需進(jìn)一步遞歸就可以解決的地步為止。
#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;
}其時間復(fù)雜度為O(2^N),由于其時間復(fù)雜度太高，在實際應(yīng)用中用武之地并沒有想象的那么多，要是真寫個這種程序，老板應(yīng)該是不容下你了。
二、空間換時間
動態(tài)開辟空間將計算出的數(shù)據(jù)記錄下來，避免重復(fù)計算，使用空間換時間。
時間復(fù)雜度O(n),空間復(fù)雜度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ù)組的大小有限制。
其缺點依然十分明顯，其空間復(fù)雜度較高，開辟堆區(qū)內(nèi)存，若管理不當(dāng)，甚至可能造成內(nèi)存泄漏。(避免因未釋放堆區(qū)而造成內(nèi)存泄漏的小技巧：(7條消息) C++11智能指針的解析_GG_Bond18的博客-CSDN博客
https://blog.csdn.net/GG_Bruse/article/details/124136480)
三、動態(tài)規(guī)劃
本方法是在方法二的基礎(chǔ)上節(jié)省空間。利用滾動數(shù)組思想，將空間復(fù)雜度由O(n)優(yōu)化為O(1)。時間復(fù)雜度依然為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ù)的時空復(fù)雜度與 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;
}時間復(fù)雜度為O(logn),空間復(fù)雜度為O(1)。
六、總結(jié)
方法一和方法二盡量不要使用。
到此這篇關(guān)于C語言深入探究斐波那契數(shù)列的文章就介紹到這了,更多相關(guān)C語言斐波那契數(shù)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了Qt實現(xiàn)屏幕底部冒泡效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
這篇文章主要為大家詳細(xì)介紹了C語言的文件操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-05-05
以下實例是對使用c++實現(xiàn)x的y次冪的解決方法進(jìn)行了介紹。需要的朋友參考下2013-05-05
C語言實現(xiàn)可增容動態(tài)通訊錄詳細(xì)過程
這篇文章主要為大家介紹了C語言實現(xiàn)簡易通訊錄的完整流程，此通訊錄還可以增容，并且每個環(huán)節(jié)都有完整代碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助2022-05-05
這篇文章主要介紹了C語言中如何利用循環(huán)嵌套輸出一個菱形問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
spdlog是一個開源、跨平臺、無依賴、只有頭文件的C++11日志庫,所以這篇文章主要來和大家介紹一下一個簡單的spdlog使用示例,感興趣的小伙伴可以了解一下2023-08-08
C++實現(xiàn)LeetCode(237.刪除鏈表的節(jié)點)
這篇文章主要介紹了C++實現(xiàn)LeetCode(237.刪除鏈表的節(jié)點),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
基于C語言實現(xiàn)創(chuàng)意多彩貪吃蛇游戲
這篇文章主要介紹了如何利用C語言實現(xiàn)一個創(chuàng)意多彩貪吃蛇游戲，這是一個純C語言外加easyx庫的繪圖函數(shù)制作而成的有趣小游戲，無需引入額外資源，感興趣的可以動手嘗試一下2022-08-08
Qt使用SQLite數(shù)據(jù)庫存儲管理圖片文件
這篇文章主要為大家詳細(xì)介紹了Qt如何使用SQLite數(shù)據(jù)庫實現(xiàn)存儲管理圖片文件的功能，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2023-04-04
Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。本文將介紹其原理，并用C++實現(xiàn)2021-06-06