斐波那契数列，求不超过四百万的偶数项之和（欧拉计划）

Question

今天我要解决的问题是：

斐波那契数列中的每一项都是通过添加前两项生成的。从 1 和 2 开始，前 10 项将是：

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

考虑斐波那契数列中不超过四百万的项，求偶数项的和

这是 Project Euler 的问题，这里是 link:

https://projecteuler.net/problem=2

我不知道我的问题是什么 code.I 认为我的逻辑是正确的，但我仍然得到错误的答案。我已经测试了 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

首先，在你的问题中你说"whose values do not exceed four million"，因为4M不超过4M所以应该是“<=4M”。但我不认为那是你的错误，最大的错误是在 main 函数中，在 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 的总和，但我的代码试图找出 2th 4th 6th 的总和...我对问题的理解有误。

斐波那契数列，求不超过四百万的偶数项之和（欧拉计划）

Fibonacci numbers,find the sum of the even-valued terms whose values do not exceed four million(Project Euler)

c

fibonacci