1 //斐波那契有好多中方法  2 #include <iostream>  3 #include <deque>  4 using namespace std;  5   6 //注意普通斐波那契，在太大数时就会发生越界，比如long long 只能存表示第92个数，这些都是小的斐波那契，当要大时，就得用大数方法了  7 //用int ，只能到第46个，47就不行了,unsighed int 只能到92  8 int fibnaq(int n)             //采用vector或者deque的方法，用2个元素的话需要用到reverse，用三个元素的话可以不用，或者用2个元素用队列也可以  9 { 10     if(n<=0) 11         return -1; 12     deque<int> d(2); 13     d[0]=1; 14     d[1]=1; 15     if(n==1||n==2) 16         return 1; 17     for(int i=3;i<=n;i++) 18     { 19         int tmp=d.front(); 20         d.pop_front(); 21         d.push_front(tmp+d.back()); 22         reverse(d.begin(),d.end()); 23     } 24     return d.back(); 25 } 26 int fibnaq2(int n)                  //数组实现,时间O(n),空间O(n) 27 { 28     int *A=new int[n]; 29     A[0]=1; 30     A[1]=1; 31     if(n==1||n==2) 32         return 1; 33     for(int i=2;i<n;i++) 34     { 35         A[i]=A[i-1]+A[i-2]; 36     } 37     delete[] A; 38     return A[n-1]; 39 } 40  41 int fibnaq3(int n)  //迭代实现，时间O(n)，空间O(1)，其实就是vector的用3个int来做，辗转相加法 42 { 43     if(n<=0) 44         return -1; 45     int a=1,b=1,c; 46     if(n==1||n==2) 47         return 1; 48     for(int i=3;i<=n;i++) 49     { 50         c=a+b; 51         a=b; 52         b=c; 53     } 54     return c; 55 } 56 long long fibnaq4(int n) //重头戏，公式法 f(n)=（(1+根号5.0）的n次方-（1-根号5.0）的n次方）/（(2.0的n次方）*根号5） 57 { 58     double gh5=sqrt(5.0); 59     return (pow(1+gh5,n)-pow(1-gh5,n))/(pow(2.0,n)*gh5); 60 } 61  62 /* 63 斐波那契数列是二阶递推数列，所以存在一个2*2的矩阵A，使得： 64 (Fn, Fn-1) = (Fn-1, Fn-2)*A 65 求得A=(1   1) 66       (1   0) 67 (fn,fn-1) = (fn-1+fn-2,fn-2) 68 (fn-1,fn-2) = (fn-1,fn-2)*A 69 ..... 70 (fn,fn-1) = (f1,f0)*A^(n-1). 71 f1=1,f0=0,f2=1. 72 只求fn，可以直接(fn,fn-1) 73 之所以能logn就是因为求幂运算可以采用二分法。 74 那么求数列的第n项就是等于求矩阵A的第n-1次幂，计算的速度非常快，时间复杂度为O(logn)。 75 首先我们用long long 型表示数列中的元素，它只能表示20位的整数，能表示的范围太小，最多第92个元素。 76 */ 77  78 void multiply(long long A[2][2],long long B[2][2],long long C[2][2]) 79 { 80     //for(int i=0;i<2;i++)                      //这样是不行的，因为有覆盖问题，还真的必须拆开写 81     //    for(int j=0;j<2;j++) 82     //        for(int k=0;k<2;k++) 83     //          C[i][j]+=A[i][k]*B[k][j]; 84     int tmp[4]; 85     tmp[0]=A[0][0]*B[0][0]+A[0][1]*B[1][0]; 86     tmp[1]=A[0][0]*B[0][1]+A[0][1]*B[1][1]; 87     tmp[2]=A[1][0]*B[0][0]+A[1][1]*B[1][0]; 88     tmp[3]=A[1][0]*B[0][1]+A[1][1]*B[1][1]; 89     C[0][0]=tmp[0]; 90     C[0][1]=tmp[1]; 91     C[1][0]=tmp[2]; 92     C[1][1]=tmp[3]; 93 } 94  95 int fibnaq5(int n)   //采用矩阵方法的O（logn） 96 { 97     if(n<=0) 98         return -1; 99     if(n<=2)100         return 1;101     long long result[2][2]={{1,0},{0,1}};             //单位阵102     long long a[2][2]={{1,1},{1,0}};103     n=n-1;                    //注意n-1次方104     while(n)105     {106         if(n&1)107             multiply(result,a,result);108         multiply(a,a,a);109         n>>=1;110     }111     return result[0][0];             //因为（1，0）*result【2】【2】，为（fn，fn-1），fn=result【0】【0】。还是看编程之美才行啊112                                                 113 114 115 //a的n次方，迭代方法116 int pow(int a,int n)          //n必须是正的，否则移位死循环117 {118  int ans=1;119  while(n)120  {121   if(n&1)             //如果n是奇数如n=5，则首次乘以a，ans=a，则移位后一直是偶数，直到最后一次，n==1时，为奇数，又把最开始的a乘上了；如果开始n是偶数，则一直未a*=a，直到最后一次，乘以1.122                         //变成除以2也可以，但是不如移位好123    ans*=a;124   a*=a;125   n>>=1;126  // n/=2;                  //用n/=2，负数不会死循环，因为-1/2=0127  }128  return ans;129 }130 131 //递归求a的n次方132 int pow2(int a,int n)133 {134     if(n==1)135         return 1;136     if(n==1)137         return a;138     int tmp=pow2(a,n/2);139     if(n&1)140         return a*tmp*tmp;141     else142         return tmp*tmp;143 }144 145 146 int main()147 {148     int n;149     cin>>n;150     cout<<fibnaq4(n)<<endl;151     //cout<<pow2(2,4)<<endl;152     system("pause");153 }