javascript 斐波那契记忆

Question

为了计算斐波那契数列的第n项，我有熟悉的递归函数：

var fibonacci = function(index){
    if(index<=0){ return 0; }
    if(index===1){ return 1; }
    if(index===2){ return 2; }

    return fibonacci(index-2) + fibonacci(index-1);
}

这按预期工作。现在，我试图将计算出的索引存储在一个对象中：

var results = {
  0: 0,
  1: 1,
  2: 2
};

var fibonacci = function(index){
    if(index<=0){ return 0; }
    if(index===1){ return 1; }
    if(index===2){ return 2; }

    if(!results[index]){
        results[index] = fibonacci(index-2) + fibonacci(index-1);
    }
}

我知道这实际上并没有提高性能，因为我没有访问结果对象，但我想在记忆之前先检查我的结果对象是否被正确填充。不幸的是，事实并非如此。对于 fibonacci(9)，我得到：

Object {0: 0, 1: 1, 2: 2, 3: 3, 4: NaN, 5: NaN, 6: NaN, 7: NaN, 8: NaN, 9: NaN}

为什么索引超过 3 时得到 NaN？

Answer 1

我添加了一些内容。

var results = {};

var fibonacci = function (index) {
   if (index <= 0) return 0;

   if (index == 1 || index == 2)  return 1;

   return fibonacci(index - 2) + fibonacci(index - 1);
};

for (var i = 1; i <= 10; i++) {
  results[i] = fibonacci(i);
}

console.log(results);

Answer 2

将通过发布@Juhana 的评论来结束此答案的循环：

"Because your function doesn't return anything when index > 2"

Answer 3

递归Fibonacci 消耗过多的处理能力，不利于应用。为了改善这一点，我们使用 Memoization。它将计算结果存储在 Array 中。所以接下来当相同的值出现时，它将简单地 return 来自计算数组的存储值。

function memoizeFabonaci(index, cache = []) {
  // console.log('index :', index, '   cache:', cache)

   if (cache[index]) {
      return cache[index] 
   }
   else {
      if (index < 3) return 1
      else {
         cache[index] = memoizeFabonaci(index - 1, cache) + memoizeFabonaci(index - 2, cache)
      }
   }
   return cache[index];

}
let a = 15
console.log('Memoize febonaci', memoizeFabonaci(a))

Answer 4

这是我的解决方案：

function fib(n, res = [0, 1, 1]) {
    if (res[n]) {
        return res[n];
    }

    res[n] = fib(n - 1, res) + fib(n - 2, res);
    return res[n];
}

console.log(fib(155));

Answer 5

这是我的解决方案

With Memoization（动态编程）（时间复杂度约为O(n)）

const results = {}

function fib(n) {
    if (n <= 1) return n

    if (n in results) {
        return results[n]
    }
    else {
        results[n] = fib(n - 2) + fib(n - 1)
    }
    return results[n]

}

console.log(fib(100))

没有Memoization（时间复杂度大约O(2^n)）

function fib(n) {
    if (n <= 1) return n

    return fib(n - 1) + fib(n - 2)

}

console.log(fib(10))

Answer 6

这是一个使用“Helper Method Recursion”的解决方案：

function fib(n) {
  const memorize = {};

  function helper(n) {
    if (n in memorize) return memorize[n];
    if (n < 3) return 1;
    return memorize[n] = helper(n - 1) + helper(n - 2);
  }

  return helper(n);
}

Answer 7

这是我面向对象的尝试。

var memofib = {
    memo : {},
    fib : function(n) {
        
        if (n === 0) {
            return 0;
        } else if (n === 1) {
            return 1;
        } else {
            
            if(this.memo[n]) return this.memo[n];
            
            return this.memo[n] = this.fib(n - 1) + this.fib(n - 2);
        }
    }
};


console.log(memofib.fib(10));

Answer 8

const f = (n, memo = [0, 1, 1]) => memo[n] ? memo[n] : (memo[n] = f(n - 1, memo) + f(n - 2, memo)) && memo[n]

console.log(f(70))

javascript 斐波那契记忆

javascript fibonacci memoization

javascript

recursion

fibonacci