一:遞歸實作
使用公式f[n]=f[n-1]+f[n-2],依序遞歸計算,遞歸結束條件是f[1]=1,f[2]=1。
二:陣列實作
空間複雜度和時間複雜度都是0(n),效率一般,比遞歸來得快。
三:vector
時間複雜度是0(n),時間複雜度是0(1),就是不知道vector的效率高不高,當然vector有自己的屬性會佔用資源。
四:queue
當然隊列比數組更適合實現斐波那契數列,時間複雜度和空間複雜度和vector
f(n)=f (n-1)+f(n-2),f(n)只和f(n-1)和f(n-2)有關,f(n)入隊列後,f(n-2)就可以出隊列了。
五:迭代實作
迭代實作是最有效率的,時間複雜度是0(n),空間複雜度是0(1)。
六:公式實現
百度的時候,發現原來斐波那契數列有公式的,所以可以使用公式來計算的。
由於double類型的精確度還不夠,所以程式算出來的結果會有誤差,如果把公式展開計算,得到的結果就是正確的。
完整的實作程式碼如下:
#include "iostream" #include "queue" #include "cmath" using namespace std; int fib1(int index) //递归实现 { if(index<1) { return -1; } if(index==1 || index==2) return 1; return fib1(index-1)+fib1(index-2); } int fib2(int index) //数组实现 { if(index<1) { return -1; } if(index<3) { return 1; } int *a=new int[index]; a[0]=a[1]=1; for(int i=2;i<index;i++) a[i]=a[i-1]+a[i-2]; int m=a[index-1]; delete a; //释放内存空间 return m; } int fib3(int index) //借用vector<int>实现 { if(index<1) { return -1; } vector<int> a(2,1); //创建一个含有2个元素都为1的向量 a.reserve(3); for(int i=2;i<index;i++) { a.insert(a.begin(),a.at(0)+a.at(1)); a.pop_back(); } return a.at(0); } int fib4(int index) //队列实现 { if(index<1) { return -1; } queue<int>q; q.push(1); q.push(1); for(int i=2;i<index;i++) { q.push(q.front()+q.back()); q.pop(); } return q.back(); } int fib5(int n) //迭代实现 { int i,a=1,b=1,c=1; if(n<1) { return -1; } for(i=2;i<n;i++) { c=a+b; //辗转相加法(类似于求最大公约数的辗转相除法) a=b; b=c; } return c; } int fib6(int n) { double gh5=sqrt((double)5); return (pow((1+gh5),n)-pow((1-gh5),n))/(pow((double)2,n)*gh5); } int main(void) { printf("%d\n",fib3(6)); system("pause"); return 0; }
七:二分矩陣方法
如上圖,Fibonacci 數列中任何一項可以用矩陣冪算出,而n次方是可以在logn的時間內算出的。
下面貼出程式碼:
void multiply(int c[2][2],int a[2][2],int b[2][2],int mod) { int tmp[4]; tmp[0]=a[0][0]*b[0][0]+a[0][1]*b[1][0]; tmp[1]=a[0][0]*b[0][1]+a[0][1]*b[1][1]; tmp[2]=a[1][0]*b[0][0]+a[1][1]*b[1][0]; tmp[3]=a[1][0]*b[0][1]+a[1][1]*b[1][1]; c[0][0]=tmp[0]%mod; c[0][1]=tmp[1]%mod; c[1][0]=tmp[2]%mod; c[1][1]=tmp[3]%mod; }//计算矩阵乘法,c=a*b int fibonacci(int n,int mod)//mod表示数字太大时需要模的数 { if(n==0)return 0; else if(n<=2)return 1;//这里表示第0项为0,第1,2项为1 int a[2][2]={{1,1},{1,0}}; int result[2][2]={{1,0},{0,1}};//初始化为单位矩阵 int s; n-=2; while(n>0) { if(n%2 == 1) multiply(result,result,a,mod); multiply(a,a,a,mod); n /= 2; }//二分法求矩阵幂 s=(result[0][0]+result[0][1])%mod;//结果 return s; }
附帶的再貼上二分法計算a的n次方函數。
int pow(int a,int n) { int ans=1; while(n) { if(n&1) ans*=a; a*=a; n>>=1; } return ans; }
更多求斐波那契(Fibonacci)數列通項的七種實現方法相關文章請關注PHP中文網!

PHP在現代Web開發中仍然重要,尤其在內容管理和電子商務平台。 1)PHP擁有豐富的生態系統和強大框架支持,如Laravel和Symfony。 2)性能優化可通過OPcache和Nginx實現。 3)PHP8.0引入JIT編譯器,提升性能。 4)雲原生應用通過Docker和Kubernetes部署,提高靈活性和可擴展性。

PHP適合web開發,特別是在快速開發和處理動態內容方面表現出色,但不擅長數據科學和企業級應用。與Python相比,PHP在web開發中更具優勢,但在數據科學領域不如Python;與Java相比,PHP在企業級應用中表現較差,但在web開發中更靈活;與JavaScript相比,PHP在後端開發中更簡潔,但在前端開發中不如JavaScript。

PHP和Python各有優勢,適合不同場景。 1.PHP適用於web開發,提供內置web服務器和豐富函數庫。 2.Python適合數據科學和機器學習,語法簡潔且有強大標準庫。選擇時應根據項目需求決定。

PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

PHP成為許多網站首選技術棧的原因包括其易用性、強大社區支持和廣泛應用。 1)易於學習和使用,適合初學者。 2)擁有龐大的開發者社區,資源豐富。 3)廣泛應用於WordPress、Drupal等平台。 4)與Web服務器緊密集成,簡化開發部署。

PHP在現代編程中仍然是一個強大且廣泛使用的工具,尤其在web開發領域。 1)PHP易用且與數據庫集成無縫,是許多開發者的首選。 2)它支持動態內容生成和麵向對象編程,適合快速創建和維護網站。 3)PHP的性能可以通過緩存和優化數據庫查詢來提升,其廣泛的社區和豐富生態系統使其在當今技術棧中仍具重要地位。

在PHP中,弱引用是通過WeakReference類實現的,不會阻止垃圾回收器回收對象。弱引用適用於緩存系統和事件監聽器等場景,需注意其不能保證對象存活,且垃圾回收可能延遲。

\_\_invoke方法允許對象像函數一樣被調用。 1.定義\_\_invoke方法使對象可被調用。 2.使用$obj(...)語法時,PHP會執行\_\_invoke方法。 3.適用於日誌記錄和計算器等場景,提高代碼靈活性和可讀性。


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

MantisBT
Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

ZendStudio 13.5.1 Mac
強大的PHP整合開發環境

EditPlus 中文破解版
體積小,語法高亮,不支援程式碼提示功能

禪工作室 13.0.1
強大的PHP整合開發環境