第二章 斐波那契之旅第2/4段
杨成很快想到了解答方法，这得益于他有经常上博客论坛向大牛请教的习惯。
在JavaScript中，对象常用作为缓存，对于斐波那契数列这样的固定序列，用全局对象来缓存是最好的方法。
（Object{}）
至于具体的逻辑，很好写：
假如缓存中没有这一项，那就缓存进去，如果存在，就直接取出来，无需重复计算。
（hash table）
JavaScript对象本质上是散列表，或者说哈希表。
所以这对象的存取效率高的令人发指，几乎可以忽略性能方面的开销了。
杨成在原本的解答上加了一些代码，用上了缓存的思想。
“这个题目加深了一些难度啊”。
杨成揉了揉太阳穴，看着那小册子再次犹如中了“浮空术”一般晃悠悠地飞向了半空中，开始了不急不慢地翻页。
他看了看窗外，那高高的塔楼顶端，还有卫兵在守卫。
这一切的一切都显得无比的真实。
他试着把手伸出窗外，却被一种无形的力量阻隔在了屋内。
一个系统音更是立刻响起：
“任务中，无法离开指定区域！”
他看了看四周，都是一些寻常人家的东西。
不过，当他看到了一个小小的架在木炭上面的咖啡壶，一个精致的骨瓷咖啡杯，还有一碗研磨得细细的咖啡粉...
杨成顿时有了一个不错的想法。
我还需要一罐香浓的鲜牛奶...
一盒高品质的方糖...
一块最好的黑巧克力...
嗯，这样就能度过一段快乐的时光。
等杨成把这些都搞到手了，他嘴角还叼着一根冒着袅袅炊烟的“软中华”。
他一下子恢复了精神，而且无比的振奋。
嘿！哥现在法力无边！
半空中，小册子的翻页速度越来越快，最后猛地一合拢，“啪嗒”一声又掉落在了桌面上。
“这下子应该结束了吧”。
杨成翻开小册子看了看。
在他刚才作答的那片区域旁边，又多了一个绿色对勾。
杨成感觉自己就像刚刚完成作业的小学生，在等着老师的批阅。
这小册子果然没有辜负他的期待。
稍等了片刻，一行行笔迹就再次出现在了空白的地方。
“啪嗒”。
香烟黯然跌落...
杨成这次终于流露出凝重的表情，这下子不是小改，是大整改了！
“依上题所述，若N在100000到400000之间，作何解？”
杨成深吸一口气。
在冷静地思考了五秒钟以后，他伸出一条长腿，把那根还未熄灭的香烟一脚踩得干瘪。
烟雾散尽，香烟愉快地终结了它的使命，进入了废纸篓。
“我大概需要这个...”
他决定了，放弃递归，使用传统的线性方法，顺序遍历求解。
这里的递归不是顺序的，斐波那契数列的递归方法是一种深度遍历求解，递归栈中函数作用域对象的开辟和回收都需要很多额外的性能开销，而顺序遍历则不存在这样的情况。
顺序遍历共享的是同一个作用域！
在早期的JavaScript中不支持块作用域，所以会共享同一个函数作用域或全局作用域。
因为公式f(n)= f(n-1)+ f(n-2)的缘故，要求第n项你只需要分别保存第n-1项和第n-2项的结果。
所以可以使用两个临时的变量来保存嘛。
这样做，将算法的空间复杂度降到了最低，和递归庞大的保存栈相比，优势就太大了。
使用循环顺序遍历，可以显著地提高速度。
而不用担心，深度递归的函数因为“爆栈”的缘故导致运行失败...
那就真是一件让人遗憾的事情呢！
想清了思路，杨成正打算提笔就写，他却突然想到了一个令人震惊的后果。
对于JavaScript，数字类型是有大小限制的。
它在内部被表示为64位的浮点数，这和Java的double数字类型是一样的。
（Number.MAX_SAFE_INTEGER）
对于第几十万项的斐波那契数，它显然已经远远超出了范围！
那么，自己的这个算法会不会导致数值溢出，从而丢失掉精度？
好在他很快就想通了，关卡设计者怎么会想不到这样的问题，自己只要能写出正确的算法来就OK了。
本章未完,请点击下一段进行阅读!