Sept façons de réaliser le terme général de la séquence de Fibonacci

1 : Implémentation récursive
Utilisez la formule f[n]=f[n-1] f[n-2] et calculez de manière récursive en séquence La condition de fin récursive est f[1]=1, f. [2]= 1.
Deux : Implémentation du tableau
La complexité spatiale et la complexité temporelle sont toutes deux de 0(n), l'efficacité est moyenne et elle est plus rapide que la récursivité.
Trois : implémentation du vecteur
La complexité temporelle est de 0(n), et la complexité temporelle est de 0(1). Je ne sais tout simplement pas si le vecteur est efficace ou non. ses propres attributs qui occuperont des ressources.
Quatre : Implémentation de la file d'attente
Bien sûr, les files d'attente sont plus adaptées à l'implémentation de séquences de Fibonacci que les tableaux. La complexité temporelle et la complexité spatiale sont les mêmes que celles du vecteur, mais les files d'attente sont parfaites pour cela, <.> f(n)=f(n-1) f(n-2), f(n) n'est lié qu'à f(n-1) et f(n-2) après que f(n) entre dans la file d'attente. , f(n -2) Vous pouvez retirer la file d'attente.
Cinq : Implémentation itérative
L'implémentation itérative est la plus efficace, avec une complexité temporelle de 0(n) et une complexité spatiale de 0(1).
Six : Implémentation de la formule
Lorsque j'étais sur Baidu, j'ai découvert que la séquence de Fibonacci a une formule, elle peut donc être calculée à l'aide de la formule.
Comme la précision du type double n'est pas suffisante, les résultats calculés par le programme comporteront des erreurs. Si la formule est développée et calculée, le résultat sera correct.
Le code d'implémentation complet est le suivant :

#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;
}

Sept : méthode matricielle bipartite

Comme indiqué ci-dessus, tout élément de la séquence de Fibonacci peut être utilisé comme matrice. Les puissances peuvent être calculées et la nième puissance peut être calculée en un temps de connexion.

Le code est affiché ci-dessous :

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;
}

Ci-joint la méthode de bissection pour calculer la nième fonction puissance de a.

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

Pour plus d'articles connexes sur les sept méthodes d'implémentation pour trouver le terme général de la séquence de Fibonacci, veuillez faire attention au site Web PHP chinois !