JavaScript解斐波那契(Fibonacci)數列的實用解法

zhongmeizhi 發布于2019-08-20 14:50 / 1475人閱讀

摘要：下面是一個可以處理很多類型遞歸函數的函數其中第一個參數為原有函數，第二個參數為緩存對象，是可選參數因為并不是所有遞歸函數都包含初始信息。首先將緩存對象的類型從數組轉換為對象，這樣就可以適用于那些不是返回整數的遞歸函數。

JavaScript解斐波那契(Fibonacci)數列的實用解法

我們經常會在面試題中看到如下題目：輸入n，求斐波那契數列的第n項，斐波那契數列的定義如下：

F(0)=0, F(1)=1, n>1時，F(n)=F(n-1)+F(n-2)。

一種效率很低的解法

當遇到這種函數時，我們很容易的想到遞歸函數，解法如下：

function fibonacci(n) {
  if(n <= 1) {return n};
  else {
    return fibonacci(n-1) + fibonacci(n-2);
  }
}

這個方法確實能解決這道題目，但遞歸的解法并不適合這道題目，用遞歸解法將會有很嚴重的效率問題，我們以f(10)為例分析一下原因：

由上述圖片我們可以看出，要想求得f(10),需要先求得f(8)和f(9)，同樣，要想求得f(9)，也要求得f(7)和f(8)。不難看出，樹結構當中很多結點是重復的，而且重復的節點數會隨著n的增大而急劇增大，這意味著計算量將會隨著n的增大而急劇增大。事實上，遞歸所需的時間復雜度是以n的指數方式遞增的，由此我們可以試試當n為100時需要耗費的時間會有多長，這是難以接受的。

動態規劃解法

造成效率低下的主要原因就是重復計算太多，我們只要想個辦法避免重復計算即可，這里有個很容易的算法：

var fib = 0,
    fib1 = 0,
    fib2 = 1;
function fibonacci(n) {
  if(n <= 1){
    return n;
  } else {
    for(var i =1; i < n; ++i) {
      fib = fib1 + fib2;
      fib1 = fib2;
      fib2 = fib;
    }
    return fib;
  }
}

理解這種方法很簡單，我們只是從下往上計算，首先根據f(0)和f(1)算出f(2),再根據f(1)和f(2)算出f(3)，依次類推我們就可以算出第n項了，而這種算法的時間復雜度僅為O(n)，比遞歸函數的寫法效率要大大增強。

Memoization

我們還可以將已經得到的數列中間項保存起來，若下次計算的時候我們先查找一下，若前面已經出現過則不用再重復計算了。

在JavaScript中，遞歸是拖慢腳本運行速度的罪魁禍首之一，太多的遞歸會讓瀏覽器越來越慢乃至奔潰，這是需要我們解決的性能問題。

我們可以使用memoization技術來替代函數中太多的遞歸調用，memoization是一種可以緩存之前運算結果的一種技術，當在執行運算操作時，我們先從緩存對象中讀取看看是否有我們需要讀取的值，若有則直接從緩存對象中讀取，若沒有則進行計算，并將緩存結果存入緩存對象中。

下面是一個可以處理很多類型遞歸函數的memoizer()函數：

`function memoizer(fun, cache) {
 cache = cache || {};
 var shell = function(arg) {
   if( ! (arg in cache)) {
     cache[arg] = fun(shell, arg);
   }
   return cache[arg];
 } ;
 return shell;
}`

其中第一個參數為原有函數，第二個參數為緩存對象，是可選參數（因為并不是所有遞歸函數都包含初始信息）。首先將緩存對象的類型從數組轉換為對象，這樣就可以適用于那些不是返回整數的遞歸函數。使用in操作符判斷參數是否已經包含在了緩存里，會比測試cache[arg]更安全些，因為undefined是一個有效的返回值(這里其實我也不太明白，弄清楚后會補上)。

接下來我們就可以調用memoizer來解這個這個問題:

var fibonacci = memoizer(function(fibon, n) {
  return fibon(n - 1) + fibon(n - 2);
}, {"0" : 0, "1" : 1});

這時我們就可以通過fibonacci(100)來執行函數，同樣運用此種方法復雜度為O(n)，大大優化了執行效率。

后記

個人更喜歡memoizer的解法，因為我覺得這種解法更加的優雅，運用了JavaScript函數式編程的特性，非常值得借鑒。

在我看來，函數的執行效率很重要，勿以事小而不為，平時多積累一些優秀的解法，從平時的小知識點出發，慢慢進步，假以時日終將也可以寫出優雅高效率的方法

云服務器 GPU云服務器波那契數列解斐波 fibonacci數列 javascript實用

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/81959.html

js 實現斐波那契數列(數組緩存、動態規劃、尾調用優化)

摘要：根據該規則，返回第個斐波那契數。尾遞歸函數調用自身，稱為遞歸。一個前端眼中的斐波那契數列解斐波那契數列的實用解法調用棧尾遞歸和手動優化尾調用優化譯我從用寫斐波那契生成器中學到的令人驚訝的件事斐波那契數列是以下一系列數字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數字 0 和 1 ...

趙連江 2019-08-23 11:38 評論0 收藏0
斐波那契數列求和的js方案以及優化

摘要：在上做了一道斐波那契數列求和的題目，做完之后做了一些簡單的優化和用另一種方法實現。動態規劃解決方案斐波那契數列求和除了可以用遞歸的方法解決，還可以用動態規劃的方法解決。在codewars上做了一道斐波那契數列求和的題目，做完之后做了一些簡單的優化和用另一種方法實現。題目 function fibonacci(n) { if(n==0 || n == 1) r...

xinhaip 2019-08-20 11:35 評論0 收藏0
斐波那契數列（求fibonacci的第N項的值）

摘要：今天在公司實習，實在沒啥活是我能干的，就想著寫一寫算法打發時間，正好看到了斐波那契數列，搞起。這是斐波那契數列的通項公式以前用遞歸寫過，今天看的時候書上說遞歸雖然簡單，但其實內部做了很多重復的計算，而且尾遞歸都是可以用循環解決的。今天在公司實習，實在沒啥活是我能干的，就想著寫一寫算法打發時間，正好看到了斐波那契數列，搞起。這是斐波那契數列的通項公式：showImg(https://...

Fundebug 2019-08-16 12:35 評論0 收藏0
使用js實現斐波那契數列

摘要：前言前幾天面試被問到了斐波那契數列的實現以及優化的問題，當時現場卡了挺久的，現在進行一下總結使用實現。題目介紹斐波那契數列又被稱為黃金分割數列，指的是這樣的一個數列，它有如下遞推的方法定義是正整數，請使用實現斐波那契函數。前言前幾天面試被問到了斐波那契數列的實現以及優化的問題，當時現場卡了挺久的，現在進行一下總結（使用js實現）。題目介紹 ??斐波那契數列又被稱為黃金分割數列，指...

alexnevsky 2019-08-26 13:36 評論0 收藏0
算法記錄 >> 斐波那契數列

摘要：今天去面試筆試題斐波那契數列實現，雖然很簡單。回來想想既然算法這么重要那就從這個開始來記錄自己的算法庫吧。在數學上，斐波納契數列以如下被以遞歸的方法定義，，。斐波拉契算法規律很簡單，，觀察下數列值就很容易總結出來了。一、寫在前面算法這塊對于大多數程序員（包括我）來說可能都是一個薄弱的地方，如何彌補尼？每個人都知道那就是學習、特別是算法沒有任何捷徑可走。在這記錄平時自己工作和生...

robin 2019-08-16 17:52 評論0 收藏0