\"[Microsoft面试]题目：定义Fibonacci 数列如下： / 0 n=0 f(n)= 1 n=1 \\ f(n-1)+f(n-2) n=2 输入n，用最快的方法求该数列的第n 项。\"

分析：在很多C 语言教科书中讲到递归函数的时候，都会用Fibonacci 作为例子。因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。

This isthe traditional problem of application of mathematics...let A={1 1}{1 0}f(n) = A^(n-1)[0,0]this gives a O(log n) solution.int f(int n) {  int A[4] = {1,1,1,0};  int result[4];  power(A, n, result);  return result[0];}voidmultiply(int[] A, int[] B, int _r) {  _r[0] = A[0]*B[0] + A[1]*B[2];  _r[1] = A[0]*B[1] + A[1]*B[3];  _r[2] = A[2]*B[0] + A[3]*B[2];  _r[3] = A[2]*B[1] + A[3]*B[3];}voidpower(int[] A, int n, int _r) {  if (n==1) { memcpy(A, _r, 4*sizeof(int)); return; }  int tmp[4];  power(A, n>>1, _r);  multiply(_r, _r, tmp);  if (n & 1 == 1) {    multiply(tmp, A, _r);  } else {    memcpy(_r, tmp, 4*sizeof(int));  }}