首頁 > web前端 > js教程 > 主體

在 JavaScript 中實作斐波那契數列:常見方法和變體

Mary-Kate Olsen
發布: 2024-09-24 06:16:32
原創
797 人瀏覽過

Implementing the Fibonacci Sequence in JavaScript: Common Approaches and Variations

作為開發人員,您可能遇到過編寫函數來計算斐波那契數列中的值的任務。這個經典問題經常出現在程式設計面試中,通常要求遞歸實現。然而,面試官有時可能會要求具體的方法。在本文中,我們將探討 JavaScript 中最常見的斐波那契數列實作。

什麼是斐波那契數列?

首先,讓我們回顧一下。斐波那契數列是一系列數字,其中每個數字都是前兩個數字的總和。以 0 和 1 開頭:

0、1、1、2、3、5、8、13、21、34、55、…

常見的實施方法

1。遞歸方法

最傳統的請求是遞歸實作:

function fibonacciRecursive(n) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
登入後複製

雖然簡單,但這種方法對於較大的 n 值來說表現不佳。在配備 16 GB RAM 的 MacBook Pro i9 上,計算第 40 個斐波那契數大約需要 1.5 秒:

console.time('Recursive');
fibonacciRecursive(40);
console.timeEnd('Recursive');

VM379:3 Recursive: 1521.569091796875 ms
登入後複製

嘗試計算第 50 個數字導致 Chrome 標籤頁無回應。

2。有緩存的遞歸方法(記憶)

這個問題的下一個變體是透過在我們的遞歸實作中加入快取機制來提高效能:

function fibonacciCached(n, cached = {[0]: 0, [1]: 1}) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  if (cached[n]) {
    return cached[n];
  }

  cached[n] = 
    fibonacciCached(n - 1, cached) + fibonacciCached(n - 2, cached);

  return cached[n];
}
登入後複製

這種方法引入了一個初始值為 0 和 1 的快取物件。對於任何給定的數字,我們首先檢查是否已經計算了其斐波那契值。如果是這樣,我們返回快取的結果而不是重新計算它。否則,我們計算該值並將其儲存在快取中。

效能提升非常顯著(當然是因為使用了額外的記憶體)。計算第 40 個斐波那契數大約需要 0.02 毫秒:

console.time('Recursive, with caching');
fibonacciCached(40);
console.timeEnd('Recursive, with caching');

VM382:3 Recursive, with caching: 0.01806640625 ms
登入後複製

3。使用 for 迴圈的迭代方法

另一個常見的變體是使用 for 迴圈實作斐波那契數列:

function fibonacciWithIteration(n) {
    if (n <= 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }

    let prev = 0;
    let next = 1;
    let result = 1;

    for (let i = 2; i <= n; i++) {
        result = prev + next;
        [prev, next] = [next, prev + next];
    }
    return result;
}
登入後複製

這種方法比基本的遞歸方法(沒有快取的方法)快得多:

console.time('With iteration');
fibonacciWithIteration(40);
console.timeEnd('With iteration');

VM44:22 With iteration: 0.10107421875 ms
登入後複製

迭代方法可以有效處理非常大的輸入值:

console.time('With iteration');
const result = fibonacciWithIteration(1400);
console.log(result);
console.timeEnd('With iteration');

VM325:22 1.7108476902340223e+292
VM325:23 With iteration: 0.5830078125 ms
登入後複製

獎勵:以數組形式傳回斐波那契數列

面試官也可能要求您以數組的形式返回直到第 n 個數字的整個斐波那契數列。讓我們使用遞歸和迭代方法來實現這一點。

遞歸方法

function fibonacciSequence(n) {
  if (n === 0) {
      return [0];
  }
  if (n === 1) {
      return [0, 1];
  }

  const arr = fibonacciSequence(n - 1);
  const currentValue = arr[n - 1] + arr[n - 2];

  return [...arr, currentValue];
}

console.log(fibonacciSequence(5)); // [0, 1, 1, 2, 3, 5]
登入後複製

函數的工作原理如下:

  1. 對於 0 和 1,我們傳回硬編碼數組。
  2. 其他情況:
  • 我們取得前一個數字的序列並將其儲存在 arr 中。
  • 我們透過將 arr 的最後兩個值相加來計算 currentValue。
  • 我們將 arr 和 currentValue 合併到一個新陣列中並傳回它。

迭代方法

function fibonacciSequenceWithIteration(n) {
  if (n < 1) {
    return [0];
  }

  let prev = 0;
  let next = 1;
  const arr = [prev, next];

  for (let i = 2; i <= n; i++) {
    arr.push(prev + next);
    [prev, next] = [next, prev + next];
  }
  return arr;
}

console.log(fibonacciSequenceWithIteration(5)); // [0, 1, 1, 2, 3, 5]
登入後複製

函數的工作原理如下:

  1. 如果輸入為 0,我們傳回一個僅包含元素 0 的陣列。
  2. 其他情況:
  • 我們初始化 prev 和 next 變數來儲存前一個和下一個值。
  • 我們建立初始值為 [0, 1] 的 arr。
  • 我們從 2 迭代到 n,在每次迭代中將 prev 和 next 的總和推入 arr。
  • 我們更新上一個和下一個值並繼續下一個迭代。

結論

雖然本文涵蓋了幾種常見的斐波那契數列實現,但它並不是詳盡的列表。如果您在採訪或工作中遇到其他變化,請在評論中分享!

隨時了解最新的 JavaScript 和軟體開發新聞!加入我的 Telegram 頻道以獲取更多見解和討論:TechSavvy:前端和後端。

以上是在 JavaScript 中實作斐波那契數列:常見方法和變體的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:dev.to
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板