作為開發人員,您可能遇到過編寫函數來計算斐波那契數列中的值的任務。這個經典問題經常出現在程式設計面試中,通常要求遞歸實現。然而,面試官有時可能會要求具體的方法。在本文中,我們將探討 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]
函數的工作原理如下:
迭代方法
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]
函數的工作原理如下:
雖然本文涵蓋了幾種常見的斐波那契數列實現,但它並不是詳盡的列表。如果您在採訪或工作中遇到其他變化,請在評論中分享!
隨時了解最新的 JavaScript 和軟體開發新聞!加入我的 Telegram 頻道以獲取更多見解和討論:TechSavvy:前端和後端。
以上是在 JavaScript 中實作斐波那契數列:常見方法和變體的詳細內容。更多資訊請關注PHP中文網其他相關文章!