使用缓存的Fibonacci

Question

这是我在CoffeeScript中的简单Fibonacci实现。你认为如何？使用缓存(fibResults)非常快。

fibResults = []
defaultMax = 1000
nrMax = defaultMax

fibonacci = (n) ->
  return fibResults[n] if fibResults[n]

  if n < 2
    fibResults[n] = n
  else
    fibResults[n] = fibonacci(n - 1) + fibonacci(n - 2)

nrMax = process.argv[2] if process.argv[2]

console.log("#{i}: #{fibonacci(i)}") for i in [0..nrMax]

Answer 1

我在您的算法中注意到的是，尽管使用了回忆法，但每次计算它时，仍然会将Fibonnacci数重新分配到数组中。

通过像computeIfAbsent这样的函数确定给定n的Fibonacci是否已经计算过，如果没有，可以使用Fibonacci函数来计算它并将其放入数组中，但这一次才是如此。

另外，我们可以避免计算前两个斐波纳契，从一开始就对它们进行回忆录，并使任何索引n小于0的代码失败。

memo = [0,1]

computeIfAbsent = (n, f) ->
    fib = memo[n]
    if typeof fib is 'undefined'
        fib = f(n)
        memo[n] = fib
    fib

fibonacci = (x) ->
    if x < 0 
        throw Error("Invalid index: " + x)
    computeIfAbsent(x, (n) -> fibonacci(n-1) +  fibonacci(n-2))

console.log("#{i}: #{fibonacci(i)}") for i in [0..79]

不过，您必须知道，此代码不会检测到算术溢出。它可能看起来是正确的计算，但实际上，计算可能是错误的，因为溢出。我认为你的版本和我的版本开始在79左右产生无效的结果。

可以使用Fibonacci计算器进行检查。

Answer 2

或者你可以做黄金配给黑客^_~ (在Javascript中)

var M = Math
  , pow = M.pow
  , round = M.round
  , phi = (M.sqrt(5)+1)/2
  , phiAnd2 = phi +2
  ;
function fib(n){
  return round(pow(phi,n)/phiAnd2)
}

虽然当fib(75) n=75 2111485077978050时，这个值仅能达到===