c - 这个算法有什么问题？

Question

我试图解决Project Euler 问题 #2：找到斐波那契数列的偶数项之和，最高可达 4,000,000。例如：最多 1000，总和为 2+8+34+144+610 = 798。

现在，我的算法是从 2 开始添加每三个斐波那契数 - 因为每三个斐波那契数必然会遵循以下逻辑：

偶数：E，奇数：O，

O+E=O    E+O=O    O+O=E
1+2=3    2+3=5    5+3=8    (example)

所以，我写了下面的代码来找出答案..

#include<stdio.h>
#define LT 4000000
int main()
{
    double i0,i1,sum=0,cycle,eSum=2,status=1;
    i0 = 1;
    i1 = 2;

    while(i1<LT && status == 1)
    {
        for(cycle=3;cycle>0;cycle--)
        {
            sum=i0+i1;
            i0=i1;
            i1=sum;

            if((i1+i0)>LT)
            {
                status = 0;
                break;
            }
        }
        eSum+=(status == 1)?sum:0;
    }
    printf("\nThe required Answer: %8.0f\n",eSum);
    return 0;
}

现在，它对于LT = 1000可以正常工作，但是对于需要 LT=4,000,000 的问题，程序会显示错误的值1089154，而不是正确的值4613732。

我无法弄清楚这段代码有什么问题。另外，我不明白它如何在 LT=1000 上正常工作，但对于更大的数字却不行。我是否遗漏了一些令人尴尬的显而易见的东西？请帮忙..

Answer 1

OP 过早退出循环。将 test 更改为sum而不是i1+i0下一个 sum。

    for(cycle=3;cycle>0;cycle--) {
        sum=i0+i1;
        i0=i1;
        i1=sum;
        // if((i1+i0)>LT)
        if(sum>LT)
        {
            status = 0;
            break;
        }
    }

由于您的数字在 [1 ... 2*4,000,000] 范围内，因此您将使用long, unsigned long, float,获得可接受的结果double。由于这是一个整数问题，建议使用整数。

Answer 2

内部 for 看起来有点奇怪，自然数不应该使用 double 。尝试这样的事情：

#include<stdio.h>
#define LT 4000000
int main()
{
  long i0,i1,sum=0,eSum=2;
  int counter = 0;
  i0 = 1;
  i1 = 1;

  while(sum<LT)
  {
    sum=i0+i1;
    i0=i1;
    i1=sum;

    eSum+=((counter++ % 3 == 0) && ( sum <= LT))?sum:0;
  }
  printf("\nThe required Answer: %8.0f\n",eSum);
  return 0;
}

Answer 3

为什么不简单地这样做呢？

#include <stdio.h>
#include <inttypes.h>
#define LT 4000000
typedef uint64_t Numtype;
int main( void )
{
    Numtype n0 = 1;
    Numtype n1 = 1;
    Numtype n2 = 0;
    Numtype sum = 0;
    for(;;)
    {
        n2 = n0 + n1;
        if ( n2 > LT ) break;
        if ( n2 % 2 == 0 ) sum += n2;
        n0 = n1;
        n1 = n2;
    }

    printf("\nThe required Answer: %ld\n", sum);
    return 0;
}