[Algorithm] Fibonacci numbers (費波那契數列)
Fibonacci numbers 說明
以下轉自維基 斐波那契数列
費氏數列由0和1開始，之後的斐波那契數就是由之前的兩數相加而得出。首幾個斐波那契數是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……（OEIS中的數列A000045）
特別指出：0不是第一項，而是第零項。
範例程式碼
Ruby 範例
附上 Ruby 的 online sandbox，有興趣可以把 code 貼進去玩玩看
def fibonacci(num)
return num if num == 0 || num == 1
fibonacci(num - 1) + fibonacci(num - 2)
end
puts fibonacci(10)
結果如下
不過這種使用遞迴的解法，複雜度是 O(n^2)
也就是說當傳入的 num 數值越大時，運算時間會呈指數成長
我們可以使用 Memoization 技巧來進行最佳化
- 檢查數字是否存在 cache 中
- 如果存在則使用 cache 中的數字
- 如不存在則將數字算出來放在 cache 中，以便之後做使用
利用這種演算法，複雜度是 O(n)
也就是說當傳入的 num 數值越大時，運算時間只會以線性成長
@cache = [0, 1]
def fibonacci(num)
return @cache[num] if @cache[num]
@cache[num] = fibonacci(num - 1) + fibonacci(num - 2)
end
puts fibonacci(10)
結果如下
JavaScript 範例
JavaScript 的 online sandbox，有興趣可以把 code 貼進去玩玩看
function fibonacci(num) {
if (num === 1 || num ===2) {
return 1
} else {
return fibonacci(num - 1) + fibonacci(num - 2)
}
}
console.log(fibonacci(10))
結果如下
使用 Memoization 技巧
function fibonacci(num, cache) {
cache = cache || {}
if (cache[num]) {
return cache[num]
}
if (num < 3) {
return 1
}
return cache[num] = fibonacci(num - 1, cache) + fibonacci(num - 2, cache)
}
console.log(fibonacci(10))
結果如下
