\"[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)this gives a O(log n) solution.int f(int n) {int A = {1,1,1,0};int result;power(A, n, result);return result;}voidmultiply(int[] A, int[] B, int _r) {_r = A*B + A*B;_r = A*B + A*B;_r = A*B + A*B;_r = A*B + A*B;}voidpower(int[] A, int n, int _r) {if (n==1) { memcpy(A, _r, 4*sizeof(int)); return; }int tmp;power(A, n>>1, _r);multiply(_r, _r, tmp);if (n & 1 == 1) { multiply(tmp, A, _r);} else { memcpy(_r, tmp, 4*sizeof(int));}}
页:
[1]