斐波那契数算法的优化

斐波那契数算法的优化

Fib(n)

{

F[0]=0;F[1]=1;

for(int i=2;i<=n;i++)

F[i]=F[i-1]+F[i-2];

return F[n];

}

比较经典的算法之一，就是上面的伪码。

可是我们仔细研究就会发现，如果我们要求Fib（10000）的值，就会产生一个很长的数组，而我们最后返回的

是数组的最后一个数。如果n的值是指数级的话，比如求 n=2^64 对应的斐波那契函数值的话，将会产生一个

多么长的数组。

但是我们真的需要这么长的数组吗？

下面是数组存放的值

0 1 1 2 3 5 8 13 21 34 55 ...

也就是如果我们求第n个斐波那契函数值，只需要求前两个斐波那契函数值，就行了！

这样的话，在求第n个数的时候，n－3，n-4,n-5...这些数就已经没有用了！

这样我们也就没有必要在数组里面保存这些数了

那么，用长度为3的数组就可以求任意大
的斐波那契数了！具体算法如下：

int Fib(int n)

{

F[0]=0;F[1]=1;

for(int i=2;i<=n;i++)

F[i%3]=F[(i-1)%3]+F[(i-2)%3];

return F[n%3];

}