Monthly Archive for September, 2011

前几天碰到一道题求斐波那契数列的非递归算法，用最简单的逐项累加，O(n)复杂度，然后被某搞过ACM的同学bs，说有O(logn)的算法。去poj上搜，果然有这个题。去wikipedia上查了下，除了F_n/F_n+1接近黄金分割比外，斐波那契数列还有一些有趣的特性，而算法便是基于这一等式：

利用二进制快速乘方(a¹¹ = a⁸.a².a =1 . a²³. 0 . a²². 1. a²¹. 1 . a²⁰)的方法，时间复杂度可成功降为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
	};
};

即使是看起来很简单的斐波那契数列，也有许多值得探究的地方。路漫漫其修远兮，吾将上下而求索