Stan Blog

記錄學習到的東西

[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)

結果如下

螢幕快照 2020-09-10 15 54 44

不過這種使用遞迴的解法,複雜度是 O(n^2)

也就是說當傳入的 num 數值越大時,運算時間會呈指數成長

我們可以使用 Memoization 技巧來進行最佳化

  1. 檢查數字是否存在 cache 中
  2. 如果存在則使用 cache 中的數字
  3. 如不存在則將數字算出來放在 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)

結果如下

螢幕快照 2020-09-11 09 19 11

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))

結果如下

螢幕快照 2020-09-10 15 59 29

使用 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))

結果如下

螢幕快照 2020-09-11 09 59 13

Comments

comments powered by Disqus