C语言求Fibonacci斐波那契数列通项问题的解法总结

#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实现 
{ 
  if(index<1) 
  { 
    return -1; 
  } 
 
  vector a(2,1);   //创建一个含有2个元素都为1的向量 
  a.reserve(3); 
  for(int i=2;iq; 
  q.push(1); 
  q.push(1); 
  for(int i=2;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; 
}//计算矩阵乘法，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; 
} 

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