資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學JavaScript中的斐波那契數列
斐波那契數列是指這樣一個數列：除前兩個數外，每個數都是其前兩個數之和。該數列以1, 1開始。例如：
1, 1, 2, 3, 5, 8, 13, 21, 34, ….
我們可以編寫一個程式來生成第n個數，如下所示：
functionfibNaive(n) {
if (n<= 1) return n;
returnfibNaive(n - 1) + fibNaive(n - 2);
}您可以使用以下方法進行測試：
console.log(fibNaive(7)); console.log(fibNaive(8)); console.log(fibNaive(9)); console.log(fibNaive(4));
這將輸出：
13 21 34 3
讓我們看看這些函式呼叫是如何實際發生的：
/** * f(5) * / \ * f(4) f(3) * / \ / \ * f(3) f(2) f(2) f(1) * / \ .......... * f(2) f(1).......... */
當我們呼叫f(5)時，我們將近4次呼叫f(2)，並且它會反覆執行相同的程式碼4次。這是一個重疊子問題的情況。嘗試對500執行該函式。您將卡住，因為所有這些呼叫都將花費大量時間。
當我們需要第5個斐波那契數時，我們只需要計算較低的斐波那契數一次，但我們計算它們的次數遠多於此。如果我們只將計算出的值儲存在某個地方，就可以減少這種冗餘計算。這就是動態規劃的關鍵。
計算一次，稍後重複使用。
讓我們看看fib函式的記憶實現。
letfibStore = {};
functionfibDP(n) {
if (n<= 1) return n;
if (fibStore[n]) {
returnfibStore[n];
}
fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
returnfibStore[n];
}現在我們使用一個儲存區fibStore來跟蹤我們已經計算出的值。這減少了過多的冗餘計算，並保持了函式的效率。
您可以使用以下方法進行測試：
console.log(fibDP(7)); console.log(fibDP(8)); console.log(fibDP(9)); console.log(fibDP(4));
這將輸出：
13 21 34 3
您甚至可以針對巨大的值測試此函式。
更新於：2020年6月22日
407 次瀏覽
廣告