fibonacci数列的余数计算

平常喜欢在交大校友足球群里吹水，这个群经常会问一些小学数学题，大部分真的很傻，然后大家还讨论得很激烈的样子，以至于我都觉得这些人怎么考上交大的…也许大部分人工作以后真的就完全不想动脑筋想什么数学题了吧。但是今天还真问了一道很有意思的题，勾起了我的兴趣，题目简化一下说是这样的：一个fibonacci数列，求第2001个数除8的余数。

这个题小学生要怎么做我不知道…但是怎么写程序我是知道的，为了显示智力上的优越感，我突然就想写代码算了显摆一下。于是code如下：

var fibo = function(N){
    if(N > 2){
	return fibo(N-1) + fibo(N-2);
    }else if(N === 2){
	return 1;
    }else if(N === 1){
	return 0;
    }else{
	return 0;
    }
}
var NUM = process.argv[2];
console.log(fibo(NUM));

然后node fibo.js 2001，然后就是等等等，我擦等了5分钟还没出来，这才想了一下算法复杂度的问题，发现这个递归算法的时间复杂度是O(2^N)的，2的2001次方…得改进一下算法，这个地方的问题是同一个数在这个算法里会被计算指数级的多次，那优化方法就是一个数只算一次，用空间换时间，于是该进后的代码如下：

var fiboArr = [];
fiboArr.push(0);
fiboArr.push(1);
for(var i = 3; i <= 2001; i++){
    fiboArr.push((fiboArr[i-2] + fiboArr[i-3]));
}

console.log(fiboArr[2000] % 8);

这个地方就是一个数组存储已经计算过的值，时间复杂度O(N)，然后运行node fibo.js，输出Infinity…数字太大越界了…尼玛看来这道题不容小觑，再想了下，我只是算余数，a + b 的余数其实等于a的余数+b的余数再取余，所以又改进了一下算法，代码如下:

var fiboArr = [];
fiboArr.push(0);
fiboArr.push(1);
for(var i = 3; i <= 2001; i++){
    fiboArr.push((fiboArr[i-2] + fiboArr[i-3])%8);
}
console.log(fiboArr[2000] % 8);

然后node fibo.js输出5，yeah~，然后微信群里简简单单发了个5，显摆到位了^-^，但是突然想到一个问题，这个题让小学生怎么做…