求斐波那契(Fibonacci)數(shù)列通項(xiàng)的七種實(shí)現(xiàn)方法
使用公式f[n]=f[n-1]+f[n-2]，依次遞歸計(jì)算，遞歸結(jié)束條件是f[1]=1，f[2]=1。
二：數(shù)組實(shí)現(xiàn)
空間復(fù)雜度和時(shí)間復(fù)雜度都是0(n)，效率一般，比遞歸來(lái)得快。
三：vector<int>實(shí)現(xiàn)
時(shí)間復(fù)雜度是0(n)，時(shí)間復(fù)雜度是0(1)，就是不知道vector的效率高不高，當(dāng)然vector有自己的屬性會(huì)占用資源。
四：queue<int>實(shí)現(xiàn)
當(dāng)然隊(duì)列比數(shù)組更適合實(shí)現(xiàn)斐波那契數(shù)列，時(shí)間復(fù)雜度和空間復(fù)雜度和vector<int>一樣，但隊(duì)列太適合這里了，
f(n)=f(n-1)+f(n-2)，f(n)只和f(n-1)和f(n-2)有關(guān)，f(n)入隊(duì)列后，f(n-2)就可以出隊(duì)列了。
五：迭代實(shí)現(xiàn)
迭代實(shí)現(xiàn)是最高效的，時(shí)間復(fù)雜度是0(n)，空間復(fù)雜度是0(1)。
六：公式實(shí)現(xiàn)
百度的時(shí)候，發(fā)現(xiàn)原來(lái)斐波那契數(shù)列有公式的，所以可以使用公式來(lái)計(jì)算的。
由于double類型的精度還不夠，所以程序算出來(lái)的結(jié)果會(huì)有誤差，如果把公式展開(kāi)計(jì)算，得出的結(jié)果就是正確的。
完整的實(shí)現(xiàn)代碼如下：
#include "iostream"
#include "queue"
#include "cmath"
using namespace std;
int fib1(int index) //遞歸實(shí)現(xiàn)
{
if(index<1)
{
return -1;
}
if(index==1 || index==2)
return 1;
return fib1(index-1)+fib1(index-2);
}
int fib2(int index) //數(shù)組實(shí)現(xiàn)
{
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; //釋放內(nèi)存空間
return m;
}
int fib3(int index) //借用vector<int>實(shí)現(xiàn)
{
if(index<1)
{
return -1;
}
vector<int> a(2,1); //創(chuàng)建一個(gè)含有2個(gè)元素都為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) //隊(duì)列實(shí)現(xiàn)
{
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) //迭代實(shí)現(xiàn)
{
int i,a=1,b=1,c=1;
if(n<1)
{
return -1;
}
for(i=2;i<n;i++)
{
c=a+b; //輾轉(zhuǎn)相加法（類似于求最大公約數(shù)的輾轉(zhuǎn)相除法）
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;
}
七：二分矩陣方法
如上圖，F(xiàn)ibonacci 數(shù)列中任何一項(xiàng)可以用矩陣冪算出，而n次冪是可以在logn的時(shí)間內(nèi)算出的。
下面貼出代碼：
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;
}//計(jì)算矩陣乘法，c=a*b
int fibonacci(int n,int mod)//mod表示數(shù)字太大時(shí)需要模的數(shù)
{
if(n==0)return 0;
else if(n<=2)return 1;//這里表示第0項(xiàng)為0，第1，2項(xiàng)為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;//結(jié)果
return s;
}
附帶的再貼上二分法計(jì)算a的n次方函數(shù)。
int pow(int a,int n)
{
int ans=1;
while(n)
{
if(n&1)
ans*=a;
a*=a;
n>>=1;
}
return ans;
}
相關(guān)文章
嵌入式項(xiàng)目使用C語(yǔ)言結(jié)構(gòu)體位段特性實(shí)現(xiàn)斷言宏校驗(yàn)數(shù)據(jù)范圍有效性的方法
今天小編就為大家分享一篇關(guān)于嵌入式項(xiàng)目使用C語(yǔ)言結(jié)構(gòu)體位段特性實(shí)現(xiàn)斷言宏校驗(yàn)數(shù)據(jù)范圍有效性的方法，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-12-12
這篇文章主要介紹了C語(yǔ)言如何改變字體顏色，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-10-10
關(guān)于C++讀入數(shù)字按位取出與進(jìn)制轉(zhuǎn)換問(wèn)題(典型問(wèn)題)
這篇文章主要介紹了關(guān)于C++讀入數(shù)字按位取出與進(jìn)制轉(zhuǎn)換問(wèn)題,是一個(gè)非常典型的問(wèn)題，本文通過(guò)實(shí)例舉例給大家介紹的非常詳細(xì)，需要的朋友可以參考下2020-02-02
C++ STL標(biāo)準(zhǔn)庫(kù)std::vector的使用詳解
vector 是表示可以改變大小的數(shù)組的序列容器，本文主要介紹了C++ STL標(biāo)準(zhǔn)庫(kù)std::vector的使用詳解，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
Eclipse中C++連接mysql數(shù)據(jù)庫(kù)
這篇文章主要為大家詳細(xì)介紹了Eclipse中C++連接mysql數(shù)據(jù)庫(kù) ，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-06-06
C++ DLL動(dòng)態(tài)庫(kù)的創(chuàng)建與調(diào)用(類庫(kù),隱式調(diào)用)
本文主要介紹了C++ DLL動(dòng)態(tài)庫(kù)的創(chuàng)建與調(diào)用(類庫(kù),隱式調(diào)用)，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要為大家詳細(xì)介紹了C++Stack棧類模版實(shí)例，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-02-02
數(shù)組是一組有序的數(shù)據(jù)的集合，數(shù)組中元素類型相同，由數(shù)組名和下標(biāo)唯一地確定，數(shù)組中數(shù)據(jù)不僅數(shù)據(jù)類型相同，而且在計(jì)算機(jī)內(nèi)存里連續(xù)存放，地址編號(hào)最低的存儲(chǔ)單元存放數(shù)組的起始元素，地址編號(hào)最高的存儲(chǔ)單元存放數(shù)組的最后一個(gè)元素2022-04-04
C++ Boost PointerContainer智能指針詳解
智能指針是一種像指針的C++對(duì)象，但它能夠在對(duì)象不使用的時(shí)候自己銷毀掉。雖然STL提供了auto_ptr，但是由于不能同容器一起使用（不支持拷貝和賦值操作），因此很少有人使用。它是Boost各組件中，應(yīng)用最為廣泛的一個(gè)2022-11-11
一文詳解C語(yǔ)言中文件相關(guān)函數(shù)的使用
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言中文件相關(guān)函數(shù)的使用，可以實(shí)現(xiàn)文件的讀寫、打開(kāi)和關(guān)閉。文中通過(guò)示例進(jìn)行了詳細(xì)介紹，需要的可以參考一下2022-07-07