题目：定义Fibonacci序列如下：f(0)=0，f(1)=f(2)=1，n>2时，f(n)=f(n-1)+f(n-2) ，输入n ，用最快的方法求该数列的第 n 项。
分析：
首先递归求法肯定都会，但是由于递推关系的形式，很容易看出里面有很多的重复计算。改进的方法也很容易想到，即申请额外的两个空间来存放保存前面的计算结果，以此来提供速度：
参考代码：
1: int getNthFibonacci(int n) 2: { 3: int first=0,second=1; 4: if(n==0 || n==1) 5: return n; 6: 7: int result=0; 8: for(int i=1;i 这里时间复杂度为O(n)，网上还有一种时间复杂度为log(n)的算法，思想如下：
其数学基础：方阵{ 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}的乘方。如果简单第从0开始循环，n次方将需要n次运算，并不比前面的方法要快。但我们可以考虑乘方的如下性质：
/ an/2*an/2 n为偶数时
an=
\ a(n-1)/2*a(n-1)/2 n为奇数时
要求得n次方，我们先求得n/2次方，再把n/2的结果平方一下。如果把求n次方的问题看成一个大问题，把求n/2看成一个较小的问题。这种把大问题分解成一个或多个小问题的思路我们称之为分治法。这样求n次方就只需要logn次运算了。
参考代码：
1: #include2: #include 3: #include //memcpy 4: 5: void multiply(int A[], int B[], int result[]) 6: { 7: result[0] = A[0]*B[0] + A[1]*B[2]; 8: result[1] = A[0]*B[1] + A[1]*B[3]; 9: result[2] = A[2]*B[0] + A[3]*B[2];10: result[3] = A[2]*B[1] + A[3]*B[3]; 11: } 12: 13: void power(int A[], int n, int result[]) 14: { 15: if (n==1) 16: { 17: memcpy(A, result, 4*sizeof(int)); 18: return; 19: } 20: int tmp[4];21: power(A, n>>1, result); 22: multiply(result, result, tmp); 23: 24: if (n & 1 == 1) 25: { 26: multiply(tmp, A, result); 27: } 28: else 29: { 30: memcpy(result, tmp, 4*sizeof(int)); 31: } 32: } 33: 34: int getNthFibonacci(int n) 35: { 36: int A[4] = {1,1,1,0};37: int result[4]={1,1,1,0}; 38: power(A, n, result);39: 40: return result[0]; 41: } 42: 43: 44: int main() 45: { 46：int n47: while(scanf("%d",&n)) 48: { 49: if(n==-1) 50: break; 51: if(n==0 || n==1) 52: printf("n=%d,result=%d\n",n,n); 53: else 54: printf("n=%d,result=%d\n",n,getNthFibonacci(n-1));55: } 56: getchar(); 57: return 0; 58: }