斐波那契数算法的优化

时间:2025-04-09

斐波那契数算法的优化

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];

}


斐波那契数算法的优化.doc 将本文的Word文档下载到电脑

    精彩图片

    热门精选

    大家正在看

    × 游客快捷下载通道(下载后可以自由复制和排版)

    限时特价:7 元/份 原价:20元

    支付方式:

    开通VIP包月会员 特价:29元/月

    注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
    微信:fanwen365 QQ:370150219