麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁 > 編程 > C > 正文

求斐波那契(Fibonacci)數(shù)列通項的七種實現(xiàn)方法

2020-01-26 16:09:56
字體:
供稿:網(wǎng)友
一:遞歸實現(xiàn)
使用公式f[n]=f[n-1]+f[n-2],依次遞歸計算,遞歸結(jié)束條件是f[1]=1,f[2]=1。
二:數(shù)組實現(xiàn)
空間復(fù)雜度和時間復(fù)雜度都是0(n),效率一般,比遞歸來得快。
三:vector<int>實現(xiàn)
時間復(fù)雜度是0(n),時間復(fù)雜度是0(1),就是不知道vector的效率高不高,當(dāng)然vector有自己的屬性會占用資源。
四:queue<int>實現(xiàn)
當(dāng)然隊列比數(shù)組更適合實現(xiàn)斐波那契數(shù)列,時間復(fù)雜度和空間復(fù)雜度和vector<int>一樣,但隊列太適合這里了,
f(n)=f(n-1)+f(n-2),f(n)只和f(n-1)和f(n-2)有關(guān),f(n)入隊列后,f(n-2)就可以出隊列了。
五:迭代實現(xiàn)
迭代實現(xiàn)是最高效的,時間復(fù)雜度是0(n),空間復(fù)雜度是0(1)。
六:公式實現(xiàn)
百度的時候,發(fā)現(xiàn)原來斐波那契數(shù)列有公式的,所以可以使用公式來計算的。
由于double類型的精度還不夠,所以程序算出來的結(jié)果會有誤差,如果把公式展開計算,得出的結(jié)果就是正確的。
完整的實現(xiàn)代碼如下:
復(fù)制代碼 代碼如下:

#include "iostream"
#include "queue"
#include "cmath"
using namespace std;
int fib1(int index)     //遞歸實現(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ù)組實現(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>實現(xiàn)
{
 if(index<1)
 {
  return -1;
 }
 vector<int> a(2,1);      //創(chuàng)建一個含有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)       //隊列實現(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)          //迭代實現(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ù)列中任何一項可以用矩陣冪算出,而n次冪是可以在logn的時間內(nèi)算出的。
下面貼出代碼:

復(fù)制代碼 代碼如下:

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表示數(shù)字太大時需要模的數(shù)
{
 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;//結(jié)果
 return s;
}

附帶的再貼上二分法計算a的n次方函數(shù)。
復(fù)制代碼 代碼如下:

int pow(int a,int n)
{
 int ans=1;
 while(n)
 {
  if(n&1)
   ans*=a;
  a*=a;
  n>>=1;
 }
 return ans;
}

發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表

圖片精選

主站蜘蛛池模板: 国产精品一区99 | 色婷婷久久一区二区 | 姑娘第四集免费看视频 | 一级性生活免费视频 | 一级免费特黄视频 | 欧美一级做a | 欧美一级黄 | 免费久久久久 | 91午夜免费视频 | 国产小视频在线 | 日本在线视 | 热99视频 | 成人免费久久网 | 国产亚洲精品影达达兔 | 伦一区二区三区中文字幕v亚洲 | 免费毛片随便看 | 亚洲精品一区二区三区大胸 | 一区二区三区在线观看免费 | 作爱在线观看 | 欧美一级三级在线观看 | 99在线精品视频免费观看20 | 成人在线视频免费播放 | 欧美日本不卡 | 日韩欧美中文字幕视频 | 一级做受大片免费视频 | 综合在线视频 | 麻豆一二区 | 国产一级在线观看视频 | 最近免费观看高清韩国日本大全 | 久久人添人人爽人人爽人人片av | 黄网站色成年大片免费高 | 亚洲午夜在线观看 | 久久久久亚洲美女啪啪 | 久久福利剧场 | 久久成人午夜视频 | 免费观看欧美一级片 | 嗯~啊~弄嗯~啊h高潮视频 | 欧美成人黄色小视频 | 国产精品白嫩白嫩大学美女 | 国产午夜精品视频免费不卡69堂 | 亚洲精品一区国产精品丝瓜 |