js:Getting 斐波那契数算法中给定整数较大时的错误答案

Question

我正在研究下面的斐波那契数列问题：

Given a positive integer num, return the sum of all odd Fibonacci numbers that are less than or equal to num. For example, sumFibs(10) should return 10 because all odd Fibonacci numbers less than or equal to 10 are 1, 1, 3, and 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 时我得到错误的总和，但其他输出是 fine.Thanks.

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

Answer 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];
}

此外，您还可以存储已经计算出的斐波那契数列，以避免重新计算的巨大负载，并节省内存和时间。

js:Getting 斐波那契数算法中给定整数较大时的错误答案

js:Getting wrong answer when given integer is bigger in Fibonacci number algorithm

javascript

algorithm

sum

fibonacci