logo标签列表

JavaScript斐波那契记忆化

javascriptrecursionfibonacci
4

为了计算斐波那契数列的第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);
    }
}

我知道这并没有实际提高性能，因为我没有访问结果对象，但在记忆化之前，我想先检查一下我的结果对象是否被正确地填充。不幸的是，它没有被正确填充。对于斐波那契数列的第九项，我得到了：

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

为什么我在索引超过 3 时会得到 NaN？
1
因为当索引大于2时，您的函数没有返回任何内容。 - JJJ
@Juhana 哦，我真傻。谢谢你。你能提交一个答案让我接受吗？ - PDN
2
不直接涉及您的问题，但是如果您正在预填充“results”数组，则为什么还需要在函数内显式测试“index”？另外，我相信“fib（2）”是“1”。 - user663031
继上一条评论后，最好从缓存中删除 2 并从代码中删除 if(index===2){ return 2; }。斐波那契数列是根据不同的要求而确定的，可以是 0, 1, 1, 2, 3, 5, 8, ... 或 1, 1, 2, 3, 5, 8, ...。请注意，在任何情况下都有两个 1。 - Scott Sauyet
9个回答
6

这里提供一种使用“辅助方法递归”解决问题的方案：

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);
}
5

这是我的解决方案：

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

递归斐波那契计算需要消耗大量的处理能力，这对应用程序不利。为了改善这种情况，我们使用记忆化。它将计算结果存储在数组中。因此，当相同值再次出现时，它将简单地从计算出的数组中返回存储的值。

function memoizeFibonacci(element, memo = {}) {
  if (element < 3) return 1;
  if (element in memo) return memo[element];

  memo[element] = memoizeFibonacci(element - 1, memo) + memoizeFibonacci(element - 2, memo);

  return memo[element];
}
let a = 15;
console.log('Memoize febonaci', memoizeFibonacci(a));

6
您在文本中正确拼写了“Fibonacci”，但代码中却没有... - Scott Sauyet
1

通过发布@Juhana的评论，将结束这个答案的循环：

“因为当索引>2时，您的函数没有返回任何内容”

1

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

1
目前你的回答不够清晰，请编辑并添加更多细节，以帮助其他人理解它如何回答问题。你可以在帮助中心找到有关如何撰写好答案的更多信息。 - Community
0

这是我的面向对象尝试。

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

0
这是我使用非递归方法实现记忆化的解决方案。
// The Fibonacci numbers.
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

function fibonacci(n) {
  const map = new Map(); // Objects can also be used
  map.set(0,1); // seed value for f(0)
  map.set(1,1); // seed value for f(1)
  for(let i=2; i < n - 1; i++) {
    const result = map.get(i - 1) + map.get(i - 2);
    map.set(i,result);
  }
  return map.get(n - 2);
}

console.log(fibonacci(20)); // 4181
0
这是我的解决方案：
使用备忘录（动态规划）（时间复杂度约为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))

没有记忆化 (时间复杂度大约为O(2^n))

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

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

}

console.log(fib(10))
-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);
这个答案没有解决原帖作者想要记忆化中间结果的需求。 - user663031
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接