Fibonacci数，找到其值不超过四百万的偶数值项的总和（Project Euler）

Question

今天我处理的问题是：

Fibonacci序列中的每个新术语都是通过添加前两个术语生成的。从1和2开始，前10个术语将是：

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

通过考虑Fibonacci序列中的值不超过四百万的项，找到偶数项的总和。

这是Project Euler的问题，这里是链接：

https://projecteuler.net/problem=2

我不知道我的代码有什么问题。我认为我的逻辑是正确的，但我仍然得到错误的答案。我测试了n <100，n <500，n <2000，我得到了正确的答案，所以我认为当n <4000000时这个代码是正确的。

这是我的代码

#include <stdio.h>

long long int Fib(int n){

    if (n == 1){

        return 1;
    }
    else if (n == 2){

        return 2;
    }
    else {
        return (Fib(n - 1) + Fib(n - 2));
    }
}

int main()
{
    int i;

    long long int sum=0;

    for(i=2;Fib(i)<4000000;i=i+2){

        sum+= Fib(i);
    }
    printf("%lld",sum);

    return 0;
}

当n <4000000时，我的答案是5702886

Answer 1

首先，在您的问题中，您说“其值不超过四百万”，因为4M不超过4M，它应该是“<= 4M”。但我不认为那是你的错，最大的错误就是在主要功能中，在for中，当你真正想要做的就是总结偶数元素时，你会跳出“i = i + 2”的步骤。斐波那契序列。不是元素列表中的偶数索引。

解决方案：这里的简单解决方案（非常低效）是将for的步骤更改为“i ++”并在if内部执行：

 if(Fib(i) % 2 == 0)
     sum += Fib(i);

额外：如果您想要修复代码以提高效率，您可以执行一些操作。如果你注意到你调用fib（i + x）时你将再次计算你之前已经完成的几次迭代。通过使用一个向量来保存斐波那契序列的每个元素，然后在最后只是对偶数的元素求和，可以很容易地解决这个问题。

编辑：这是一个示例替代（更有效）的解决方案：谨慎使用：未经测试可能会有小错误。

    int main(){

    int fibbs[4000000]; // it will never be bigger than this
    int sum = 0;
    int numValues = 0; // counts the number of values in the vector

   // initialize vector to 0's , probably not necessary
    for(i = 0; i < 4000000; i++){
        fibs[i] = 0;
    }

    // first positions of fibonacci
    fibs[0] = 1;
    fibs[1] = 1;
    fibs[2] = 2;



    // fill the vector with all the fibonacci numbers until 4M
    int i = 3;
    while(1){
        fibs[i] = fibs[i-1] + fibs[i-2];
        if(fibs[i] > 4000000){
            fibs[i] = 0; // it is already bigger than 4M , can't sum this one
            numValues = i-1; // save the number of values in the vector
            break;
        }
        i++;
    }

    for(i = 0; i <= numValues; i++){
        if(fibs[i] % 2 == 0 ){
            sum += fibs[i];
        }
    }

    printf("Sum is: %d\n", sum);
    return 0;

    }

Answer 2

我知道我的错误在哪里。问题想要一个Fib（i）％2 == 0的总和，但是我的代码试图找出第2个第4个第6个的总和......我对问题进行了错误的解释。