第四章 十万级斐波那契 (第1/2页)

“依上题所述，若N在100000到400000之间，作何解？”
　　
　　杨成深吸一口气，他明白自己此前的思路已经走到了尽头，必须得换一种方式了。
　　
　　对于递归而言，十万级以上是遥不可及的一道天堑，不管怎样使劲，都只有一种结局——挂。
　　
　　所以，他决定了，放弃递归，使用传统的线性方法，顺序遍历求解。
　　
　　递归不是顺序的，斐波那契数列的分治法是一种深度遍历求解，递归栈中函数作用域对象的开辟和回收都需要很多额外的性能，而顺序遍历不存在这样的情况。
　　
　　顺序遍历共享的是同一个作用域！
　　
　　可以使用两个临时的变量，因为公式f(n)=f(n-1)+f(n-2)的缘故，要求第n项你只需要分别保存第n-1项和第n-2项的结果。
　　
　　这样做，将算法的空间复杂度降到了最低，和递归庞大的保存栈相比，优势就太大了。
　　
　　想清了思路，杨成正打算提笔就写，他突然想到一个令人震惊的后果。
　　
　　对于JavaScript，浮点数是有大小限制的，对于第几十万项的斐波那契数，它显然已经远远超出了浮点型的范围，那么，自己这个算法会不会导致溢出？
　　
　　好在他很快想通了，关卡设计者怎么会想不到这样的问题，自己只要能写出正确的算法来就OK了。
　　
　　这个算法其实并不难，杨成用了十几行代码就搞定了，他心里其实还是有些忐忑的，作为一名准程序员，有这种意识其实还是挺正常的。
　　
　　不是有个笑话吗，假如有人问一名程序员：你的程序是不是出Bug了？这个程序员听到后第一反应是：傻x你懂程序嘛？你会用嘛？而如果有人问程序员：这个效果和预期的有些不一致呢。那程序员肯定心想：糟了！肯定是出Bug了！
　　
　　

（本章未完，请点击下一页继续阅读）