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

首頁 > 編程 > C > 正文

求斐波那契(Fibonacci)數列通項的七種實現方法

2020-01-26 16:09:56
字體:
來源:轉載
供稿:網友
一:遞歸實現
使用公式f[n]=f[n-1]+f[n-2],依次遞歸計算,遞歸結束條件是f[1]=1,f[2]=1。
二:數組實現
空間復雜度和時間復雜度都是0(n),效率一般,比遞歸來得快。
三:vector<int>實現
時間復雜度是0(n),時間復雜度是0(1),就是不知道vector的效率高不高,當然vector有自己的屬性會占用資源。
四:queue<int>實現
當然隊列比數組更適合實現斐波那契數列,時間復雜度和空間復雜度和vector<int>一樣,但隊列太適合這里了,
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;
}

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

圖片精選

主站蜘蛛池模板: 亚洲第五色综合网 | 久色网站| 成人在线免费小视频 | 亚洲码无人客一区二区三区 | 香蕉视频1024 | 精品无吗乱吗av国产爱色 | 成人在线观看免费观看 | 成人毛片av在线 | 日韩精品一区二区三区中文 | 欧美成人国产va精品日本一级 | 全网免费毛片 | 毛片区| 毛片一区二区三区四区 | 一级免费毛片 | sm高h视频| 成人男女视频 | 亚洲第一男人天堂 | 日韩av手机在线免费观看 | 国产正在播放 | 亚洲欧美国产精品va在线观看 | 精品国产一区二区三区久久久蜜月 | 男女羞羞的视频 | 欧美成人影院 | 羞羞网站在线看 | 成人福利在线视频 | 成人免费一区二区三区在线观看 | 国产瑟瑟视频 | 新久草在线视频 | 操操日日| 爱爱插插视频 | 99久久婷婷国产综合精品青牛牛 | 亚洲自拍第一 | 91视频久久 | 91国内精品久久久久免费影院 | 91美女视频在线观看 | 久久精品视频网址 | 日本高清无遮挡 | 一级一级一级一级毛片 | 中国老女人一级毛片视频 | 欧美a区 | 亚洲成人精品久久久 |