编程代码之战：第2章 斐波那契之旅
第2章 斐波那契之旅
神圣罗马帝国皇室图书馆，海量的书架井然有序，一位头戴王冠的中年男子和一位学者在这里促膝长谈。
此时夜深人静，牛油烛散发出柔和的光芒，勉强能照亮一小块区域。
“斐波那契，你这个兔子问题，寡人想了很久都没有头绪”。
中年男子挠了挠头。
腓特烈二世生平最大的业余爱好便是研究数学。
而眼前这位学者，便是他的座上客，大名鼎鼎的斐波那契。
“兔生二月便能繁衍，视为成兔...”
“假定初月有一对幼兔，每月每对成兔可生一对幼兔，则一年后，可得兔几何？”
腓特烈自言自语着，沉浸其中。
（1，1，2，3...）
“二月之后可新生一对兔，故三月为两对兔，四月幼兔不足两月，无法繁殖，故为三对兔，以此类推...”
斐波那契耐心地解答道。
“哈哈哈哈！”
“爱卿果然才思敏捷！”
腓特烈二世竖起了大拇指，眼中满是赞赏之色。
“孤欲编纂算书，卿可为之...”
话说完，君臣两人离席。
斐波那契走在回住所的路上，脑海中却在回想刚才谈话的内容，似乎有所明悟。
“何不将该类问题，阐述为通项公式？”
他喃喃自语。
回到住所，斐波那契赶紧打开一个小册子，拿起鹅毛笔蘸了蘸墨水，写下刚才的想法。
“若有f(0)为0，f(1)为1，则f(n)为f(n-1)与f(n-2)之和”。
斐波那契抬头看了看窗外的月光，月下的树梢之上，停留着一只枯叶蝶。
那蝴蝶似乎有所感应，循着灯光，翩翩飞舞。
斐波那契还在专注地思考着，根本没有察觉这只蝴蝶正朝着他飞过来。
蝴蝶飞过窗台，然后轻轻地落在了斐波那契的肩头。
下一刻，它消失了，杨成的意识出现在了斐波那契脑海中。
“哇！”
杨成惊讶地看着自己这身古欧洲的学者服饰，摸了摸下巴。
他感觉自己的体貌特征来了个180度的大转变。
眼前的小册子在烛光下浮现出一行行字，顿时吸引了杨成的注意力。
“已知斐波那契通项公式f(n)=f(n-1)+f(n-2)，编写求第N项斐波那契数的函数，N在20以内...”
杨成瞪大了眼睛，这里连电脑都没有，只有一支鹅毛笔，怎么写啊？
手写？
似乎问题也不是很大，求20项以内的斐波那契数，完全可以用简单的递归啊！
杨成回忆了一下，然后用鹅毛笔蘸了蘸墨水，在小册子上写下了寥寥几行。
这是一种“教科书式”的求解：
要求第N项，那么就分解为求第N-1项和第N-2项...
那N-1项又可以分解为求N-2和N-3项...
以此类推，直到N为0，返回0，N为1，返回1。
但这种方法之所以被称作教科书式，一是因为通俗易懂，二是因为效率很低下。
它求重复的项数太多了，或者说重复计算太多了，是一个指数级的算法。
杨成很清楚这种方法的弊端，但应付20以内的小数据量，绰绰有余哩！
果不其然，在杨成写完最后一个括号以后，手中的小册子绽放出一道金光。
不会爆出史诗装备来吧？
小册子犹如脱离了重力的束缚一般，慢慢浮空，它一页接一页地自动翻页，就好比有人在翻阅一般。
“啪嗒”。
小册子掉落在了桌子上，金光收敛，什么奇迹也没有发生...
杨成定睛一看，发现自己刚才手写的解题方法旁边多了一个小小的绿色对勾。
“唉，没啥挑战性啊”。
据说是萌新程序员必写的代码排行Top10...
杨成活动了一下筋骨。
这厮话音刚落。
然后，他看到那个小册子自动地翻过了一页，上面又浮现了一些笔迹。
“依上题，若N大于10000，且小于20000，作何解？”
杨成念完这新内容，皱了皱眉头。
“传统的递归方法求斐波那契数列，只限于小数求解，到了上万的数量级再用一般的递归，效率低不说，还有可能导致递归栈溢出”。
因为每次递归调用的时候，都会在栈里储存方法的参数、局部变量、返回值，像这样的一些信息。
而栈空间是有限的，像在早期的Windows系统中为1M大小。
所以，成千上万个此类信息空间累积起来，就容易爆掉它。
“那么，如何在原来的代码上面做修改，来达到提高性能的目的呢？”
杨成思索了片刻。
“既然递归方法慢的根本原因，在于重复性的计算太多，那么我可以使用缓存！”
杨成很快想到了解答方法，这得益于他有经常上博客论坛向大牛请教的习惯。
（Object{}）
在JavaScript中，对象常用作为缓存，对于斐波那契数列这样的固定序列，用一个全局对象来缓存是比较合适的方法。
至于具体的逻辑，很好写：
假如缓存中没有这一项，那就缓存进去；如果存在，就直接把值取出来，无需重复计算。
（hash table）
JavaScript对象本质上是散列表，或者说哈希表。
所以这对象的存取效率高的很，都只需要常量时间，几乎可以忽略性能方面的开销了。
杨成在原本的解答上加了一些代码，用上了缓存的思想。
“这个题目加深了一些难度啊”。
杨成揉了揉太阳穴，看着那小册子再次犹如中了浮空术一般，晃悠悠地飞向了半空中，开始了不急不慢地翻页。
他看了看窗外，在那高高的塔楼顶端，还有卫兵在守卫。
这一切的一切都显得无比的真实。
他尝试着把手伸出窗外，却被一种无形的力量阻隔在了屋内。
一个系统音更是立刻响起：
“任务中，无法离开指定区域！”
他看了看四周，都是一些寻常人家的东西。
不过，当他看到了一个小小的架在木炭上面的咖啡壶，一个精致的骨瓷咖啡杯，还有一碗研磨得细细的咖啡粉...
杨成顿时有了个不错的想法。
我还需要一罐香浓的鲜牛奶...
一盒高品质的方糖...
一块最好的黑巧克力...
嗯，这样就能度过一段快乐的时光。
等杨成把这些都搞到手了，他嘴角还叼着一根冒着袅袅炊烟的软中华。
他一下子恢复了精神，而且无比的振奋。
嘿嘿，哥现在法力无边！
半空中，小册子的翻页速度越来越快，最后猛地一合拢，“啪嗒”一声过后，又掉落在了桌面上。
“这下子应该结束了吧”。
杨成翻开册子瞅了瞅。
在他刚才作答的那片区域旁边，又多了一个绿色对勾。
杨成感觉自己就像刚刚完成作业的一名小学生，在等着老师的批阅...
这小册子果然没有辜负他的期待，稍等了片刻，一行行笔迹就再次出现在了空白的地方。
“啪嗒”。
他手上的香烟黯然跌落...
杨成这次终于流露出一份凝重的表情，因为，这下子不是小修改，是大整改了！
“依上题所述，若N在100000到400000之间，作何解？”
杨成深吸一口气，在冷静地思考了五秒钟以后，他伸出一条长腿，把那根还未熄灭的香烟，一脚踩得干瘪。
烟雾散尽，香烟愉快地终结了它的使命，进入了废纸篓。
“我大概需要这个...”
他决定了，放弃递归，使用传统的线性方法，顺序遍历求解。
这里的递归不是顺序的，斐波那契数列的递归方法是一种深度遍历求解，递归栈中函数作用域对象的开辟和回收都需要很多额外的性能开销。
（Scope）
而顺序遍历则不存在这样的情况，它共享的是同一个作用域！
在早期的JavaScript中不支持块作用域，所以会共享同一个函数作用域或全局作用域。
因为公式f(n)= f(n-1)+ f(n-2)的缘故，要求第n项你只需要分别保存第n-1项和第n-2项的结果。
所以，可以使用两个临时的变量来保存，也就是只需要常量空间。
这样做，将算法的空间复杂度降到了最低，和递归庞大的保存栈相比，优势就太大了。
使用循环顺序遍历，可以显著地提高速度。
而不用担心，深度递归的函数因为“爆栈”的缘故导致运行失败...
那就真是一件让人遗憾的事情呢！
想清了思路，杨成正打算提笔就写，他却突然想到了一个令人震惊的后果。
对于JavaScript，数字类型是有大小限制的。
它在内部被表示为64位的浮点数，这和Java的double数字类型是一样的。
（Number.MAX_SAFE_INTEGER）
对于第几十万项的斐波那契数，它显然已经远远超出了范围！
那么，自己的这个算法会不会导致数值溢出，从而丢失掉精度？
好在他很快就想通了，关卡设计者怎么会考虑不到这样的问题，自己只要能写出正确的算法来就OK了。
在较新的JS标准中，提供了BigInt类型，可以做大整数的运算。
各种浏览器均已支持，语法很简洁，像这样：
BigInt(“10”)
或是更简单的定义：
10n
所以可以这样做1+1：
1n+1n
-----------------------
请知晓：它的各种操作，比方说加减乘除，不是常数时间复杂度的，只是给俺们提供便利的“语法糖”。
解释器会帮我们做转换~
-----------------------
这个方法其实并不难，杨成用十几行代码就搞定了。
小册子第三次浮空...
杨成舒服地打了个哈欠。
时间过得很慢...
这次小册子被翻页的时间和次数都多得多，显然和数据量大小有关系。
杨成甚至有些怀疑，是一台286电脑在充当服务器处理~
现代电脑有这么辣鸡嘛？
是不是并发量太大了，服务器被挤爆了的缘故呢？
（真相：这游戏确实是一个人开发维护的）
等到杨成开始怀疑这个小册子组件模块编写者，这厮性别取向问题的时候，小册子终于完成了它的使命…
“玛德，至少过去了半个钟头”。
杨成嘟哝着，再次翻开小册子某一页。
刚才写的那十几行代码旁边，又多了一个小小的对勾。
然而，还没来得及为自己高超的“手写代码”能力欢呼雀跃，杨成很快看到了让自己张大嘴巴的一个景象。
“嚯！”
他不禁倒吸了一口凉气。
随后，这厮犹如泄了气的皮球一般，倒在了后椅上。
“先前的思路又得改！”
“依上所述”。
这字迹依旧在忠实地记录着题目。
“若N在800000到1200000之间，作何解？”
这是一个典型的算法问题，要求高性能。
斐波那契传统的通项公式，已经无法满足这种需求了，或者说，已经被时代的前沿所抛弃了。
一般的通项公式面对这个问题，就如同蜗牛一样爬行，让人无法忍受。
需要用到的海量大整数加法运算，足以摧毁这种算法脆弱的体系。
这也恰恰体现了时代的局限性，毕竟斐波那契时代距今也相差近千年了。
杨成闭着眼睛，开始回忆以前在网上搜索的那一个个例子。
斐波那契矩阵，两倍项公式渐渐浮现在他的脑海中。
杨成嘴角咧出一丝笑意。
既然f(n)的公式不行，那就用f(2n)的公式！
他思索了片刻，用鹅毛笔蘸了蘸墨水，写下了一行公式：
f(2n)=f(n-1)f(n)+f(n+1)f(n)
这是一个对数级的算法，可以胜任大数据的挑战。
具体的代码他没有写，因为他并没有办法来验证程序的正确性，至于做单元测试，那更是想都别想。
令人惊讶的事情很快就发生了…
这个两倍项公式被一个椭圆的金色线条所环绕着，最后，旁边也出现了个对勾。
“叮！”
一声清脆的系统铃音响起。
“恭喜玩家您连续完成了阶段性任务，请休息一刻钟，我们将为您准备该系列的最后一项挑战！”
“唉”，杨成感觉有些乏味了。
这些题目确实比较益智，但总是一个人做，是不是太单调了？
于是，他灵机一动，打开玩家面板，选中了客服按钮。
“你好，很高兴为您服务！自助服务请按0，人工服务请按1”。
杨成选择了“1”。
“我是客服小美，请问您有什么问题嘛？”
那边传来了甜甜的妹子声音。
“唉呀，美女啊”。
这厮顿时来了兴致。
“我觉得你们的题目设计的很不错，但我有一个小小的建议啊”。
“请讲”。
客服妹子有耐心地问道。
“你看我一个人，穿着这样的奇装异服，在这里默默地做着题目，多枯燥啊”。
杨成摇摆着腿。
“嗯”，客服妹子表示理解。
“能不能安排一个类似于泰坦尼克号的双人解题环节，给俺试试啊”。
杨成坏坏地笑了。
“嗯...”
妹子有些无语了，这人真是想象力Max啊。
“好的，您的需求我们会尽可能考虑的”。
她体现了良好的职业素质。
“请问您还有什么需要帮助的嘛？”
“没了，我就想和漂亮姐姐你聊聊天啊”。
杨成脸上的笑意更浓烈了。
（这厮要准备耍流氓了）
“能不能和我真人视频哪？”
“祝您游戏愉快，再见，嘀，嘀...”
通讯设备那边见势不妙，很快就挂断了。
杨成有些不死心，再次选择了客服按钮。
“您拨打的客服热线正忙，请稍后再试...”
“您拨打的客服热线正忙，请稍后再试...”
“法克！”
杨成两手一摊，垂头丧气的。
So boring...
好在时间过得很快，一刻钟一下子就过去了。
杨成翻了翻小册子，很快发现了最后一道斐波那契系列的题目。
“这？”
杨成挠了挠头，这问题还真没有想过啊。
“让我想想，这该怎么算呢？”
他撕下一张纸，作为草稿，在上面演算起来。
还是做题目有意思...
“依上所述，若N为负数项，作何解？”
这字迹感觉是一个固定的格式，开头是“依上所述”，中间是“若N为X项”，后面则是“作何解？”。
杨成有点鄙视这个出题的人了，你就不能来一点新意嘛？
“求负数项有意义嘛？”
他不禁道出了心中的疑问。
比如说f(-1)，这该怎么求呢？
杨成把f(-1)写在了f(0)和f(1)旁边，他仔仔细细地观察，很快发现了规律。
f(-1)不就是f(1)减去f(0)嘛！
f(-2)不就是f(0)减去f(-1)嘛！
那么，以此类推，将公式f(n)= f(n-1)+ f(n-2)简单变换一下，就能得到：
f(n-2)= f(n)- f(n-1)
这不就是负数项公式了吗？
杨成把负数项公式填到小册子上，把它刚刚合上…
“噼啪噼啪！”
3D成像菜单顿时烟花齐放，系统制作的掌声如雷，系统声音也及时地响了起来。
“恭喜您成功完成了斐波那契之旅所有阶段的任务，您获得的积分明细如下”。
“初始积分2分”。
“递归方法完成斐波那契数列求解奖励2分”。
“缓存提高算法效率奖励2分”。
“线性求解奖励2分”。
“两倍项公式求解奖励5分”。
“负数项求解奖励2分”。
“现今共有积分15分，击败了全球10%的玩家，希望您再接再厉！”
杨成则是有些疲惫地抬了抬眼皮。
这些题目实在是太耗费脑力和体力了，自己都有些支撑不住了。
有必要吃个炒粉，喝点功能性维生素饮料，否则营养跟不上的话，怎么继续开车？
老司机又不是铁打的！
“请问您要继续挑战下一个关卡嘛？”
系统声音提示道。
“不必了，直接Esc吧”。
杨成摆了摆手。
“好的，祝您生活愉快，再见！”
眼前的世界骤然变黑，又瞬间恢复了视野，杨成摘掉VR头盔，揉了揉发酸的眼睛。
他这才发现网吧外面已经是一片漆黑，再不回去，估计寝室大门就关闭了。
对于翻墙这类问题，杨成还真不擅长，程序猿可不是猿猴…
在网吧楼下的小餐馆买了一份炒粉打包，再买了几瓶饮料，杨成这才走回了寝室。
室友们都在自己的笔记本前，玩一款流行了十多年的单机横版格斗游戏：
“毒奶粉”
杨成见状顿时耸耸肩，他大声嚷嚷道。
“这特么都二十年代了，你们还玩这08年出来的单机网游，太Out了吧？”
室友们愤愤不平地比了个中指，然后自顾自地玩去了。
杨成自讨了个没趣，便在书架里翻了又翻，摸索了半天后，他拿出一本不太薄也不太厚的《C专家编程》。
随后，这厮一个翻身爬上了铺位。
你说他挑这本经典书是为何？
莫不是想拿来装X？
非也，非也，你说这大日光灯下，不拿本书遮脸挡光，能睡得着嘛？
太厚了可压得生疼哩！
杨成把那《C专家编程》分开成两半，盖在脸上，闭上了眼睛。
他实在是太累了，很快便进入了睡梦中，与周公相会。