Seven realization methods of the general term of Fibonacci sequence

One: recursive implementation
Using formula f [n] = f (n - 1) + f (n - 2), in turn, the recursive calculation, recursive end conditions [1] is f = 1, f [2] = 1.
Two: array implementation
The space complexity and the time complexity are both 0(n), and the efficiency is average, which is faster than recursion.
3: the vector < int > implementation
The time complexity is 0(n), and the time complexity is 0(1). I don't know whether the vector is efficient or not.
Four: the queue < int > implementation
Of course, queues are better than arrays for implementing Fibonacci sequences, time complexity and space complexity and vectors < int > Same thing, but the queue is perfect for this,
F (n) = f (n - 1) + f (n - 2), f (n) and f (n - 1) and f (n - 2), f (n) into the queue, f (n - 2) can be out of the queue.
Five: iterative implementation
Iterative implementations are the most efficient, with time complexity of 0(n) and space complexity of 0(1).
Six: formula realization
Baidu, found that the original Fibonacci sequence has a formula, so you can use the formula to calculate.
Since the precision of double type is not enough, the result calculated by the program will have errors. If the formula is expanded, the result is correct.
The complete implementation code is as follows:

#include "iostream"
#include "queue"
#include "cmath"
using namespace std;
int fib1(int index)     //The recursive implementation
{
 if(index<1)
 {
  return -1;
 }
 if(index==1 || index==2)
  return 1;
 return fib1(index-1)+fib1(index-2);
}
int fib2(int index)     //Array implementation
{
 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;         //Free memory space
 return m;
}
int fib3(int index)           //Borrow vector<Int> implementation
{
 if(index<1)
 {
  return -1;
 }
 vector<int> a(2,1);      //Create a vector that has two elements that are all 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)       //Queue implementation
{
 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)          //Iteration implement
{
 int i,a=1,b=1,c=1;
 if(n<1)
 {
  return -1;
 }
 for(i=2;i<n;i++)
 {
  c=a+b;     //Toss and turn (similar to the toss and turn division to find the greatest common divisor)
  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("%dn",fib3(6));
 system("pause");
 return 0;
}

Seven: binary matrix method

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201305/201305240940433.gif ">

As shown in the figure above, any term in the Fibonacci sequence can be calculated by matrix powers, while the n power can be calculated in logn time.
Post the code below:

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;
}//So if you multiply the matrix, c is equal to a times b
int fibonacci(int n,int mod)//The mod represents the number that needs to be modulated if the number is too large
{
 if(n==0)return 0;
 else if(n<=2)return 1;//This is saying that the 0th term is 0, and the 1st and 2nd terms are 1
 int a[2][2]={{1,1},{1,0}};
 int result[2][2]={{1,0},{0,1}};//Initialize it as the identity matrix
 int s;
 n-=2;
 while(n>0)
 {
  if(n%2 == 1)
   multiply(result,result,a,mod);
  multiply(a,a,a,mod);
  n /= 2;
 }//The dichotomy takes the power of the matrix
 s=(result[0][0]+result[0][1])%mod;//The results of
 return s;
}

I'm going to attach a dichotomy to compute a to the n.

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