第二章 斐波那契之旅

　　神圣羅馬帝國皇室圖書館，海量的書架井然有序，一位頭戴王冠的中年男子和一位學(xué)者在這里促膝長談。

　　此時夜深人靜，牛油燭散發(fā)出柔和的光芒，勉強能照亮一小塊區(qū)域。

　　“斐波那契，你這個兔子問題，寡人想了很久都沒有頭緒”。

　　中年男子撓了撓頭。

　　腓特烈二世生平最大的業(yè)余愛好便是研究數(shù)學(xué)。

　　而眼前這位學(xué)者，便是他的座上客，大名鼎鼎的斐波那契。

　　“兔生二月便能繁衍，視為成兔...”

　　“假定初月有一對幼兔，每月每對成兔可生一對幼兔，則一年后，可得兔幾何？”

　　腓特烈自言自語著，沉浸其中。

　?。?，1，2，3...）

　　“二月之后可新生一對兔，故三月為兩對兔，四月幼兔不足兩月，無法繁殖，故為三對兔，以此類推...”

　　斐波那契耐心地解答道。

　　“哈哈哈哈！”

　　“愛卿果然才思敏捷！”

　　腓特烈二世豎起了大拇指，眼中滿是贊賞之色。

　　“孤欲編纂算書，卿可為之...”

　　話說完，君臣兩人離席。

　　斐波那契走在回住所的路上，腦海中卻在回想剛才談話的內(nèi)容，似乎有所明悟。

　　“何不將該類問題，闡述為通項公式？”

　　他喃喃自語。

　　回到住所，斐波那契趕緊打開一個小冊子，拿起鵝毛筆蘸了蘸墨水，寫下剛才的想法。

　　“若有f(0)為0，f(1)為1，則f(n)為f(n-1)與f(n-2)之和”。

　　斐波那契抬頭看了看窗外的月光，月下的樹梢之上，停留著一只枯葉蝶。

　　那蝴蝶似乎有所感應(yīng)，循著燈光，翩翩飛舞。

　　斐波那契還在專注地思考著，根本沒有察覺這只蝴蝶正朝著他飛過來。

　　蝴蝶飛過窗臺，然后輕輕地落在了斐波那契的肩頭。

　　下一刻，它消失了，楊成的意識出現(xiàn)在了斐波那契腦海中。

　　“哇！”

　　楊成驚訝地看著自己這身古歐洲的學(xué)者服飾，摸了摸下巴。

　　他感覺自己的體貌特征來了個180度的大轉(zhuǎn)變。

　　眼前的小冊子在燭光下浮現(xiàn)出一行行字，頓時吸引了楊成的注意力。

　　“已知斐波那契通項公式f(n)=f(n-1)+f(n-2)，編寫求第N項斐波那契數(shù)的函數(shù)，N在20以內(nèi)...”

　　楊成瞪大了眼睛，這里連電腦都沒有，只有一支鵝毛筆，怎么寫??？

　　手寫？

　　似乎問題也不是很大，求20項以內(nèi)的斐波那契數(shù)，完全可以用簡單的遞歸啊！

　　楊成回憶了一下，然后用鵝毛筆蘸了蘸墨水，在小冊子上寫下了寥寥幾行。

　　這是一種“教科書式”的求解：

　　要求第N項，那么就分解為求第N-1項和第N-2項...

　　那N-1項又可以分解為求N-2和N-3項...

　　以此類推，直到N為0，返回0，N為1，返回1。

　　但這種方法之所以被稱作教科書式，一是因為通俗易懂，二是因為效率很低下。

　　它求重復(fù)的項數(shù)太多了，或者說重復(fù)計算太多了，是一個指數(shù)級的算法。

　　楊成很清楚這種方法的弊端，但應(yīng)付20以內(nèi)的小數(shù)據(jù)量，綽綽有余哩！

　　果不其然，在楊成寫完最后一個括號以后，手中的小冊子綻放出一道金光。

　　不會爆出史詩裝備來吧？

　　小冊子猶如脫離了重力的束縛一般，慢慢浮空，它一頁接一頁地自動翻頁，就好比有人在翻閱一般。

　　“啪嗒”。

　　小冊子掉落在了桌子上，金光收斂，什么奇跡也沒有發(fā)生...

　　楊成定睛一看，發(fā)現(xiàn)自己剛才手寫的解題方法旁邊多了一個小小的綠色對勾。

　　“唉，沒啥挑戰(zhàn)性啊”。

　　據(jù)說是萌新程序員必寫的代碼排行Top10...

　　楊成活動了一下筋骨。

　　這廝話音剛落。

　　然后，他看到那個小冊子自動地翻過了一頁，上面又浮現(xiàn)了一些筆跡。

　　“依上題，若N大于10000，且小于20000，作何解？”

　　楊成念完這新內(nèi)容，皺了皺眉頭。

　　“傳統(tǒng)的遞歸方法求斐波那契數(shù)列，只限于小數(shù)求解，到了上萬的數(shù)量級再用一般的遞歸，效率低不說，還有可能導(dǎo)致遞歸棧溢出”。

　　因為每次遞歸調(diào)用的時候，都會在棧里儲存方法的參數(shù)、局部變量、返回值，像這樣的一些信息。

　　而?？臻g是有限的，像在早期的Windows系統(tǒng)中為1M大小。

　　所以，成千上萬個此類信息空間累積起來，就容易爆掉它。

　　“那么，如何在原來的代碼上面做修改，來達到提高性能的目的呢？”

　　楊成思索了片刻。

　　“既然遞歸方法慢的根本原因，在于重復(fù)性的計算太多，那么我可以使用緩存！”

　　楊成很快想到了解答方法，這得益于他有經(jīng)常上博客論壇向大牛請教的習(xí)慣。

　?。∣bject{}）

　　在JavaScript中，對象常用作為緩存，對于斐波那契數(shù)列這樣的固定序列，用一個全局對象來緩存是比較合適的方法。

　　至于具體的邏輯，很好寫：

　　假如緩存中沒有這一項，那就緩存進去；如果存在，就直接把值取出來，無需重復(fù)計算。

　　（hash table）

　　JavaScript對象本質(zhì)上是散列表，或者說哈希表。

　　所以這對象的存取效率高的很，都只需要常量時間，幾乎可以忽略性能方面的開銷了。

　　楊成在原本的解答上加了一些代碼，用上了緩存的思想。

　　“這個題目加深了一些難度啊”。

　　楊成揉了揉太陽穴，看著那小冊子再次猶如中了浮空術(shù)一般，晃悠悠地飛向了半空中，開始了不急不慢地翻頁。

　　他看了看窗外，在那高高的塔樓頂端，還有衛(wèi)兵在守衛(wèi)。

　　這一切的一切都顯得無比的真實。

　　他嘗試著把手伸出窗外，卻被一種無形的力量阻隔在了屋內(nèi)。

　　一個系統(tǒng)音更是立刻響起：

　　“任務(wù)中，無法離開指定區(qū)域！”

　　他看了看四周，都是一些尋常人家的東西。

　　不過，當他看到了一個小小的架在木炭上面的咖啡壺，一個精致的骨瓷咖啡杯，還有一碗研磨得細細的咖啡粉...

　　楊成頓時有了個不錯的想法。

　　我還需要一罐香濃的鮮牛奶...

　　一盒高品質(zhì)的方糖...

　　一塊最好的黑巧克力...

　　嗯，這樣就能度過一段快樂的時光。

　　等楊成把這些都搞到手了，他嘴角還叼著一根冒著裊裊炊煙的軟中華。

　　他一下子恢復(fù)了精神，而且無比的振奮。

　　嘿嘿，哥現(xiàn)在法力無邊！

　　半空中，小冊子的翻頁速度越來越快，最后猛地一合攏，“啪嗒”一聲過后，又掉落在了桌面上。

　　“這下子應(yīng)該結(jié)束了吧”。

　　楊成翻開冊子瞅了瞅。

　　在他剛才作答的那片區(qū)域旁邊，又多了一個綠色對勾。

　　楊成感覺自己就像剛剛完成作業(yè)的一名小學(xué)生，在等著老師的批閱...

　　這小冊子果然沒有辜負他的期待，稍等了片刻，一行行筆跡就再次出現(xiàn)在了空白的地方。

　　“啪嗒”。

　　他手上的香煙黯然跌落...

　　楊成這次終于流露出一份凝重的表情，因為，這下子不是小修改，是大整改了！

　　“依上題所述，若N在100000到400000之間，作何解？”

　　楊成深吸一口氣，在冷靜地思考了五秒鐘以后，他伸出一條長腿，把那根還未熄滅的香煙，一腳踩得干癟。

　　煙霧散盡，香煙愉快地終結(jié)了它的使命，進入了廢紙簍。

　　“我大概需要這個...”

　　他決定了，放棄遞歸，使用傳統(tǒng)的線性方法，順序遍歷求解。

　　這里的遞歸不是順序的，斐波那契數(shù)列的遞歸方法是一種深度遍歷求解，遞歸棧中函數(shù)作用域?qū)ο蟮拈_辟和回收都需要很多額外的性能開銷。

　?。⊿cope）

　　而順序遍歷則不存在這樣的情況，它共享的是同一個作用域！

　　在早期的JavaScript中不支持塊作用域，所以會共享同一個函數(shù)作用域或全局作用域。

　　因為公式f(n)= f(n-1)+ f(n-2)的緣故，要求第n項你只需要分別保存第n-1項和第n-2項的結(jié)果。

　　所以，可以使用兩個臨時的變量來保存，也就是只需要常量空間。

　　這樣做，將算法的空間復(fù)雜度降到了最低，和遞歸龐大的保存棧相比，優(yōu)勢就太大了。

　　使用循環(huán)順序遍歷，可以顯著地提高速度。

　　而不用擔心，深度遞歸的函數(shù)因為“爆?！钡木壒蕦?dǎo)致運行失敗...

　　那就真是一件讓人遺憾的事情呢！

　　想清了思路，楊成正打算提筆就寫，他卻突然想到了一個令人震驚的后果。

　　對于JavaScript，數(shù)字類型是有大小限制的。

　　它在內(nèi)部被表示為64位的浮點數(shù)，這和Java的double數(shù)字類型是一樣的。

　?。∟umber.MAX_SAFE_INTEGER）

　　對于第幾十萬項的斐波那契數(shù)，它顯然已經(jīng)遠遠超出了范圍！

　　那么，自己的這個算法會不會導(dǎo)致數(shù)值溢出，從而丟失掉精度？

　　好在他很快就想通了，關(guān)卡設(shè)計者怎么會考慮不到這樣的問題，自己只要能寫出正確的算法來就OK了。

　　在較新的JS標準中，提供了BigInt類型，可以做大整數(shù)的運算。

　　各種瀏覽器均已支持，語法很簡潔，像這樣：

　　BigInt(“10”)

　　或是更簡單的定義：

　　10n

　　所以可以這樣做1+1：

　　1n+1n

　　-----------------------

　　請知曉：它的各種操作，比方說加減乘除，不是常數(shù)時間復(fù)雜度的，只是給俺們提供便利的“語法糖”。

　　解釋器會幫我們做轉(zhuǎn)換~

　　-----------------------

　　這個方法其實并不難，楊成用十幾行代碼就搞定了。

　　小冊子第三次浮空...

　　楊成舒服地打了個哈欠。

　　時間過得很慢...

　　這次小冊子被翻頁的時間和次數(shù)都多得多，顯然和數(shù)據(jù)量大小有關(guān)系。

　　楊成甚至有些懷疑，是一臺286電腦在充當服務(wù)器處理~

　　現(xiàn)代電腦有這么辣雞嘛？

　　是不是并發(fā)量太大了，服務(wù)器被擠爆了的緣故呢？

　?。ㄕ嫦啵哼@游戲確實是一個人開發(fā)維護的）

　　等到楊成開始懷疑這個小冊子組件模塊編寫者，這廝性別取向問題的時候，小冊子終于完成了它的使命…

　　“瑪?shù)?，至少過去了半個鐘頭”。

　　楊成嘟噥著，再次翻開小冊子某一頁。

　　剛才寫的那十幾行代碼旁邊，又多了一個小小的對勾。

　　然而，還沒來得及為自己高超的“手寫代碼”能力歡呼雀躍，楊成很快看到了讓自己張大嘴巴的一個景象。

　　“嚯！”

　　他不禁倒吸了一口涼氣。

　　隨后，這廝猶如泄了氣的皮球一般，倒在了后椅上。

　　“先前的思路又得改！”

　　“依上所述”。

　　這字跡依舊在忠實地記錄著題目。

　　“若N在800000到1200000之間，作何解？”

　　這是一個典型的算法問題，要求高性能。

　　斐波那契傳統(tǒng)的通項公式，已經(jīng)無法滿足這種需求了，或者說，已經(jīng)被時代的前沿所拋棄了。

　　一般的通項公式面對這個問題，就如同蝸牛一樣爬行，讓人無法忍受。

　　需要用到的海量大整數(shù)加法運算，足以摧毀這種算法脆弱的體系。

　　這也恰恰體現(xiàn)了時代的局限性，畢竟斐波那契時代距今也相差近千年了。

　　楊成閉著眼睛，開始回憶以前在網(wǎng)上搜索的那一個個例子。

　　斐波那契矩陣，兩倍項公式漸漸浮現(xiàn)在他的腦海中。

　　楊成嘴角咧出一絲笑意。

　　既然f(n)的公式不行，那就用f(2n)的公式！

　　他思索了片刻，用鵝毛筆蘸了蘸墨水，寫下了一行公式：

　　f(2n)=f(n-1)f(n)+f(n+1)f(n)

　　這是一個對數(shù)級的算法，可以勝任大數(shù)據(jù)的挑戰(zhàn)。

　　具體的代碼他沒有寫，因為他并沒有辦法來驗證程序的正確性，至于做單元測試，那更是想都別想。

　　令人驚訝的事情很快就發(fā)生了…

　　這個兩倍項公式被一個橢圓的金色線條所環(huán)繞著，最后，旁邊也出現(xiàn)了個對勾。

　　“叮！”

　　一聲清脆的系統(tǒng)鈴音響起。

　　“恭喜玩家您連續(xù)完成了階段性任務(wù)，請休息一刻鐘，我們將為您準備該系列的最后一項挑戰(zhàn)！”

　　“唉”，楊成感覺有些乏味了。

　　這些題目確實比較益智，但總是一個人做，是不是太單調(diào)了？

　　于是，他靈機一動，打開玩家面板，選中了客服按鈕。

　　“你好，很高興為您服務(wù)！自助服務(wù)請按0，人工服務(wù)請按1”。

　　楊成選擇了“1”。

　　“我是客服小美，請問您有什么問題嘛？”

　　那邊傳來了甜甜的妹子聲音。

　　“唉呀，美女啊”。

　　這廝頓時來了興致。

　　“我覺得你們的題目設(shè)計的很不錯，但我有一個小小的建議啊”。

　　“請講”。

　　客服妹子有耐心地問道。

　　“你看我一個人，穿著這樣的奇裝異服，在這里默默地做著題目，多枯燥啊”。

　　楊成搖擺著腿。

　　“嗯”，客服妹子表示理解。

　　“能不能安排一個類似于泰坦尼克號的雙人解題環(huán)節(jié)，給俺試試啊”。

　　楊成壞壞地笑了。

　　“嗯...”

　　妹子有些無語了，這人真是想象力Max啊。

　　“好的，您的需求我們會盡可能考慮的”。

　　她體現(xiàn)了良好的職業(yè)素質(zhì)。

　　“請問您還有什么需要幫助的嘛？”

　　“沒了，我就想和漂亮姐姐你聊聊天啊”。

　　楊成臉上的笑意更濃烈了。

　?。ㄟ@廝要準備耍流氓了）

　　“能不能和我真人視頻哪？”

　　“祝您游戲愉快，再見，嘀，嘀...”

　　通訊設(shè)備那邊見勢不妙，很快就掛斷了。

　　楊成有些不死心，再次選擇了客服按鈕。

　　“您撥打的客服熱線正忙，請稍后再試...”

　　“您撥打的客服熱線正忙，請稍后再試...”

　　“法克！”

　　楊成兩手一攤，垂頭喪氣的。

　　So boring...

　　好在時間過得很快，一刻鐘一下子就過去了。

　　楊成翻了翻小冊子，很快發(fā)現(xiàn)了最后一道斐波那契系列的題目。

　　“這？”

　　楊成撓了撓頭，這問題還真沒有想過啊。

　　“讓我想想，這該怎么算呢？”

　　他撕下一張紙，作為草稿，在上面演算起來。

　　還是做題目有意思...

　　“依上所述，若N為負數(shù)項，作何解？”

　　這字跡感覺是一個固定的格式，開頭是“依上所述”，中間是“若N為X項”，后面則是“作何解？”。

　　楊成有點鄙視這個出題的人了，你就不能來一點新意嘛？

　　“求負數(shù)項有意義嘛？”

　　他不禁道出了心中的疑問。

　　比如說f(-1)，這該怎么求呢？

　　楊成把f(-1)寫在了f(0)和f(1)旁邊，他仔仔細細地觀察，很快發(fā)現(xiàn)了規(guī)律。

　　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)

　　這不就是負數(shù)項公式了嗎？

　　楊成把負數(shù)項公式填到小冊子上，把它剛剛合上…

　　“噼啪噼啪！”

　　3D成像菜單頓時煙花齊放，系統(tǒng)制作的掌聲如雷，系統(tǒng)聲音也及時地響了起來。

　　“恭喜您成功完成了斐波那契之旅所有階段的任務(wù)，您獲得的積分明細如下”。

　　“初始積分2分”。

　　“遞歸方法完成斐波那契數(shù)列求解獎勵2分”。

　　“緩存提高算法效率獎勵2分”。

　　“線性求解獎勵2分”。

　　“兩倍項公式求解獎勵5分”。

　　“負數(shù)項求解獎勵2分”。

　　“現(xiàn)今共有積分15分，擊敗了全球10%的玩家，希望您再接再厲！”

　　楊成則是有些疲憊地抬了抬眼皮。

　　這些題目實在是太耗費腦力和體力了，自己都有些支撐不住了。

　　有必要吃個炒粉，喝點功能性維生素飲料，否則營養(yǎng)跟不上的話，怎么繼續(xù)開車？

　　老司機又不是鐵打的！

　　“請問您要繼續(xù)挑戰(zhàn)下一個關(guān)卡嘛？”

　　系統(tǒng)聲音提示道。

　　“不必了，直接Esc吧”。

　　楊成擺了擺手。

　　“好的，祝您生活愉快，再見！”

　　眼前的世界驟然變黑，又瞬間恢復(fù)了視野，楊成摘掉VR頭盔，揉了揉發(fā)酸的眼睛。

　　他這才發(fā)現(xiàn)網(wǎng)吧外面已經(jīng)是一片漆黑，再不回去，估計寢室大門就關(guān)閉了。

　　對于翻墻這類問題，楊成還真不擅長，程序猿可不是猿猴…

　　在網(wǎng)吧樓下的小餐館買了一份炒粉打包，再買了幾瓶飲料，楊成這才走回了寢室。

　　室友們都在自己的筆記本前，玩一款流行了十多年的單機橫版格斗游戲：

　　“毒奶粉”

　　楊成見狀頓時聳聳肩，他大聲嚷嚷道。

　　“這特么都二十年代了，你們還玩這08年出來的單機網(wǎng)游，太Out了吧？”

　　室友們憤憤不平地比了個中指，然后自顧自地玩去了。

　　楊成自討了個沒趣，便在書架里翻了又翻，摸索了半天后，他拿出一本不太薄也不太厚的《C專家編程》。

　　隨后，這廝一個翻身爬上了鋪位。

　　你說他挑這本經(jīng)典書是為何？

　　莫不是想拿來裝X？

　　非也，非也，你說這大日光燈下，不拿本書遮臉擋光，能睡得著嘛？

　　太厚了可壓得生疼哩！

　　楊成把那《C專家編程》分開成兩半，蓋在臉上，閉上了眼睛。

　　他實在是太累了，很快便進入了睡夢中，與周公相會。