学步园

<pre name="code" class="cpp">/*
第 19  题： 
题目：定义 Fibonacci  数列如下：
f(n)=1 n=0
f(n)= 1 n=1
f(n-1)+f(n-2) n=2
输入n,用最快的方法求该数列的第 n 项。

基本的方法有2种

还有个网上方法： 
其数学基础：
方阵{ f(n), f(n-1), f(n-1), f(n-2) } = {1, 1, 1,0 }n-1方 
即前者表示一个2X2的方阵，
后者表示一个第一行为1,1、第二行为1,0的方阵的n-1次方。
矩阵{1,1,1,0}的n-1次方的结果的第一行第一列就是f(n)，


现在的问题转换为求矩阵{1, 1, 1, 0}的乘方。

但我们可以考虑乘方的如下性质：
        /   an/2*an/2                      n为偶数时 
an= 
        \  a(n-1)/2*a(n-1)/2              n为奇数时
要求得n次方，我们先求得n/2次方，再把n/2的结果平方一下。

分治法。求n变为2个n/2 
这样求n次方就只需要logn次运算了。
*/

#include <iostream>  
using namespace std;  
   
// 递归方法，时间复杂度O(n)  
int Fibonacci1(int n)  
{  
    if (n==0||n==1)  
        return n;  
    else  
        return Fibonacci1(n-1)+Fibonacci1(n-2);  
}  
   
// 额外空间循环方法，时间复杂度O(n)  
int Fibonacci2(int n)  
{  
    int result=0;  
    int f1=0,f2=1;
	 
    if (n==0||n==1)  
        return n;  
    else  
    {  
        for (int i=1;i<n;i++)  
        {  
            result=f1+f2;  
            f1=f2;  
            f2=result;  
        }  
    }  
    return result;  
}  


void multiply(int A[], int B[], int result[])  
{ 
     result[0] = A[0]*B[0] + A[1]*B[2]; 
     result[1] = A[0]*B[1] + A[1]*B[3]; 
     result[2] = A[2]*B[0] + A[3]*B[2]; 
     result[3] = A[2]*B[1] + A[3]*B[3]; 
} 

void power(int A[], int n, int result[])  
 { 
    if (n==1)  
     {  
        memcpy(A,result,4*sizeof(int));  
        return;  
     } 
     int tmp[4]; 
     power(A, n>>1,result); 
     multiply(result,result,tmp); 
  
     if (n&1==1)  
     { 
          multiply(tmp, A, result); 
     }  
     else  
     { 
        memcpy(result,tmp,4*sizeof(int)); 
     } 
} 
 int Fibonacci3(int n)  
 { 
     int A[4] = {1,1,1,0}; 
     int result[4]={1,1,1,0}; 
     power(A, n, result); 
     return result[0];
 } 
 
int main()  
{  
    cout<<Fibonacci2(10)<<endl;  
    cout<<Fibonacci1(10)<<endl;  
    cout<<Fibonacci3(10-1)<<endl;  
    return 0;  
}