前几天碰到一道题求斐波那契数列的非递归算法，用最简单的逐项累加，O(n)复杂度，然后被某搞过ACM的同学bs，说有O(logn)的算法。去poj上搜，果然有这个题。去wikipedia上查了下，除了Fn/Fn+1接近黄金分割比外，斐波那契数列还有一些有趣的特性，而算法便是基于这一等式：
利用二进制快速乘方(a11 = a8.a2.a =1 . a23. 0 . a22. 1. a21. 1 . a20)的方法，时间复杂度可成功降为O(logn)
poj3070,给定n(0<=n<= 1,000,000,000), 输出Fn模10000的值
代码如下：
//poj 3070
//Triton
#include <stdio.h>
//mod 10000 以减小数值范围
int matrixMultiply(long *a, long *b, long *answer)
{
long tmp[4];
tmp[0] = (a[0] * b[0] + a[1] * b[2])%10000;
tmp[1] = (a[0] * b[1] + a[1] * b[3])%10000;
tmp[2] = (a[2] * b[0] + a[3] * b[2])%10000;
tmp[3] = (a[2] * b[1] + a[3] * b[3])%10000;
int i;
for(i = 0; i < 4; ++i){
answer[i] = tmp[i];
}
return 0;
}
int matrixPower(long n, long *answer)
{
int i;
if(n < 0){
for(i = 0; i < 4; ++i) answer[i] = 0;
}
else{
long pre[4];
long cur[4] = {1,1,1,0};
long res = n;
long rem = res % 2;
answer[0] = 1;
answer[1] = 0;
answer[2] = 0;
answer[3] = 1; //初始化为单位矩阵
//利用二进制快速乘方
while(res != 0){
if(rem == 1) matrixMultiply(cur,answer,answer);
i = 0;
for(i = 0; i < 4; ++i){
pre[i] = cur[i];
}
matrixMultiply(pre, pre, cur);
res >>= 1;
rem = res % 2;
}
}
return 0;
}
int main()
{
long num;
long answer[4];
while(1){
scanf("%ld",&num);
if(num != -1){
matrixPower(num,answer);
printf("%d\n", answer[1]%10000);
}
else break;
}
return 0;
}
同学看我做这个题，给了另一个模板编程的代码（汗，从来没用过），好处是运行很快，据说游戏中经常用类似的模板编程
#define Fib(N) FibT<N>::Val
template<int n> struct FibT
{
enum
{
Val = FibT<n-1>::Val + FibT<n-2>::Val
};
};
template<> struct FibT<0>
{
enum
{
Val = 0
};
};
template<> struct FibT<1>
{
enum
{
Val = 1
};
};
即使是看起来很简单的斐波那契数列，也有许多值得探究的地方。路漫漫其修远兮，吾将上下而求索
