首页 文章

js：给定整数时得到的错误答案在Fibonacci数算法中更大

提问于
浏览 次
-3

我正在研究下面的Fibonacci数字问题：

给定正整数num，返回小于或等于num的所有奇数Fibonacci数的总和 . 例如，sumFibs（10）应该返回10，因为小于或等于10的所有奇数Fibonacci数都是1,1,3和5 .

sumFibs(1) should return a number.
sumFibs(1000) should return 1785.
sumFibs(4000000) should return 4613732.
sumFibs(4) should return 5.
sumFibs(75024) should return 60696.
sumFibs(75025) should return 135721.

以下是我的解决方案 . 我很困惑为什么当给定的整数num等于4000000时，我得到的总和总和，但其他输出都很好 . 谢谢 .

function FindFib(num){   
    if(num === 0)
       return 0;    
    else if(num === 1)
       return 1;    
    else
       return FindFib(num-2) + FindFib(num-1); 
}

function sumFibs(num) {    
  var total=0;   
  var fib=0;

  for(var i =0;i<=num;i++){

    fib = FindFib(i);

    if(fib%2 === 1 && fib <= num)
      total=total+fib;         
   }
     return total;    
}

console.log(sumFibs(400000));
javascript algorithm sum fibonacci

1 回答

  • 1

    由于斐波那契数字很快变大，FindFib方法将无法工作 .

    注意，如果第n个斐波纳契数大于任何数字X，则第n个第1个斐波那契数也大于X.考虑到这一点，我们可以在找到超过N的第一个斐波纳契数时停下来 .

    所以我们可以重写 sumFibs 方法，

    function sumFibs(num) {    
  var total=0;   
  var fib=0;
  for(var i = 0;i <= num; i++){
    fib = FindFib(i);
    if(fib > num)break;
    if(fib%2 === 1)
      total=total+fib;         
   }
   return total;    
}

    您还可以通过迭代方法找到第n个斐波那契数，这很简单，

    function findFib(n) {
    let fib = [];
    fib[0] = 1
    fib[1] = 1
    for(int i = 2; i <= n; ++i) {
        fib[i] = fib[i-1]+fib[i-2];
    }
    return fib[n];
}

    此外，您可以存储已计算的斐波纳契数，以避免大量重新计算，并节省内存和时间 .

    回复于

相关问题