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

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

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

　　中年男子撓了撓頭。

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

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

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

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

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

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

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

　　斐波那契耐心地解答道,。

　　“哈哈哈哈,！”

　　“愛卿果然才思敏捷！”

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

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

　　話說完，君臣兩人離席,。

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

　　“何不將該類問題,，闡述為通項(xiàng)公式？”

　　他喃喃自語,。

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

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

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

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

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

　　蝴蝶飛過窗臺(tái),，然后輕輕地落在了斐波那契的肩頭。

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

　　“哇,！”

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

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

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

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

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

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

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

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

　　要求第N項(xiàng)，那么就分解為求第N-1項(xiàng)和第N-2項(xiàng)...

　　那N-1項(xiàng)又可以分解為求N-2和N-3項(xiàng)...

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

　　但這種方法之所以被稱作教科書式，一是因?yàn)橥ㄋ滓锥?，二是因?yàn)樾屎艿拖隆?p>　　它求重復(fù)的項(xiàng)數(shù)太多了,，或者說重復(fù)計(jì)算太多了，是一個(gè)指數(shù)級(jí)的算法,。

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

　　果不其然,，在楊成寫完最后一個(gè)括號(hào)以后,，手中的小冊(cè)子綻放出一道金光,。

　　不會(huì)爆出史詩裝備來吧？

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

　　“啪嗒”,。

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

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

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

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

　　楊成活動(dòng)了一下筋骨,。

　　這廝話音剛落。

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

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

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

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

　　因?yàn)槊看芜f歸調(diào)用的時(shí)候，都會(huì)在棧里儲(chǔ)存方法的參數(shù),、局部變量,、返回值，像這樣的一些信息,。

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

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

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

　　楊成思索了片刻,。

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

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

　?。∣bject{}）

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

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

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

　　（hash table）

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

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

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

　　“這個(gè)題目加深了一些難度啊”,。

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

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

　　這一切的一切都顯得無比的真實(shí),。

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

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

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

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

　　不過,，當(dāng)他看到了一個(gè)小小的架在木炭上面的咖啡壺,，一個(gè)精致的骨瓷咖啡杯,，還有一碗研磨得細(xì)細(xì)的咖啡粉...

　　楊成頓時(shí)有了個(gè)不錯(cuò)的想法。

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

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

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

　　嗯,，這樣就能度過一段快樂的時(shí)光,。

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

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

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

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

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

　　楊成翻開冊(cè)子瞅了瞅,。

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

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

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

　　“啪嗒”。

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

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

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

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

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

　　“我大概需要這個(gè)...”

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

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

　?。⊿cope）

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

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

　　因?yàn)楣絝(n)= f(n-1)+ f(n-2)的緣故，要求第n項(xiàng)你只需要分別保存第n-1項(xiàng)和第n-2項(xiàng)的結(jié)果,。

　　所以,，可以使用兩個(gè)臨時(shí)的變量來保存，也就是只需要常量空間,。

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

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

　　而不用擔(dān)心,，深度遞歸的函數(shù)因?yàn)椤氨瑮！钡木壒蕦?dǎo)致運(yùn)行失敗...

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

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

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

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

　　（Number.MAX_SAFE_INTEGER）

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

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

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

　　在較新的JS標(biāo)準(zhǔn)中，提供了BigInt類型,，可以做大整數(shù)的運(yùn)算,。

　　各種瀏覽器均已支持，語法很簡(jiǎn)潔,，像這樣：

　　BigInt(“10”)

　　或是更簡(jiǎn)單的定義：

　　10n

　　所以可以這樣做1+1：

　　1n+1n

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

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

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

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

　　這個(gè)方法其實(shí)并不難，楊成用十幾行代碼就搞定了,。

　　小冊(cè)子第三次浮空...

　　楊成舒服地打了個(gè)哈欠,。

　　時(shí)間過得很慢...

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

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

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

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

　　（真相：這游戲確實(shí)是一個(gè)人開發(fā)維護(hù)的）

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

　　“瑪?shù)拢辽龠^去了半個(gè)鐘頭”,。

　　楊成嘟噥著,，再次翻開小冊(cè)子某一頁。

　　剛才寫的那十幾行代碼旁邊,，又多了一個(gè)小小的對(duì)勾,。

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

　　“嚯！”

　　他不禁倒吸了一口涼氣,。

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

　　“先前的思路又得改,！”

　　“依上所述”。

　　這字跡依舊在忠實(shí)地記錄著題目,。

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

　　這是一個(gè)典型的算法問題,，要求高性能,。

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

　　一般的通項(xiàng)公式面對(duì)這個(gè)問題，就如同蝸牛一樣爬行,，讓人無法忍受,。

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

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

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

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

　　楊成嘴角咧出一絲笑意,。

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

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

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

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

　　具體的代碼他沒有寫，因?yàn)樗]有辦法來驗(yàn)證程序的正確性,，至于做單元測(cè)試,，那更是想都別想。

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

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

　　“叮,！”

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

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

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

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

　　于是,，他靈機(jī)一動(dòng),，打開玩家面板，選中了客服按鈕,。

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

　　楊成選擇了“1”,。

　　“我是客服小美,，請(qǐng)問您有什么問題嘛？”

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

　　“唉呀,，美女啊”。

　　這廝頓時(shí)來了興致,。

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

　　“請(qǐng)講”,。

　　客服妹子有耐心地問道,。

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

　　楊成搖擺著腿,。

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

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

　　楊成壞壞地笑了。

　　“嗯...”

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

　　“好的，您的需求我們會(huì)盡可能考慮的”,。

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

　　“請(qǐng)問您還有什么需要幫助的嘛？”

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

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

　?。ㄟ@廝要準(zhǔn)備耍流氓了）

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

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

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

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

　　“您撥打的客服熱線正忙，請(qǐng)稍后再試...”

　　“您撥打的客服熱線正忙,，請(qǐng)稍后再試...”

　　“法克,！”

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

　　So boring...

　　好在時(shí)間過得很快,，一刻鐘一下子就過去了。

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

　　“這？”

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

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

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

　　還是做題目有意思...

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

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

　　楊成有點(diǎn)鄙視這個(gè)出題的人了,，你就不能來一點(diǎn)新意嘛,？

　　“求負(fù)數(shù)項(xiàng)有意義嘛？”

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

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

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

　　f(-1)不就是f(1)減去f(0)嘛！

　　f(-2)不就是f(0)減去f(-1)嘛,！

　　那么,，以此類推，將公式f(n)= f(n-1)+ f(n-2)簡(jiǎn)單變換一下,，就能得到：

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

　　這不就是負(fù)數(shù)項(xiàng)公式了嗎,？

　　楊成把負(fù)數(shù)項(xiàng)公式填到小冊(cè)子上，把它剛剛合上…

　　“噼啪噼啪,！”

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

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

　　“初始積分2分”,。

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

　　“緩存提高算法效率獎(jiǎng)勵(lì)2分”,。

　　“線性求解獎(jiǎng)勵(lì)2分”,。

　　“兩倍項(xiàng)公式求解獎(jiǎng)勵(lì)5分”。

　　“負(fù)數(shù)項(xiàng)求解獎(jiǎng)勵(lì)2分”,。

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

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

　　這些題目實(shí)在是太耗費(fèi)腦力和體力了，自己都有些支撐不住了,。

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

　　老司機(jī)又不是鐵打的！

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

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

　　“不必了，直接Esc吧”,。

　　楊成擺了擺手,。

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

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

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

　　對(duì)于翻墻這類問題，楊成還真不擅長(zhǎng),，程序猿可不是猿猴…

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

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

　　“毒奶粉”

　　楊成見狀頓時(shí)聳聳肩，他大聲嚷嚷道,。

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

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

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

　　隨后,，這廝一個(gè)翻身爬上了鋪位。

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

　　莫不是想拿來裝X,？

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

　　太厚了可壓得生疼哩,！

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

　　他實(shí)在是太累了，很快便進(jìn)入了睡夢(mèng)中,，與周公相會(huì),。