1

我尝试了很多次，但我似乎无法弄清楚我做错了什么。这是我最近尝试解决的问题之一。

我知道其他来源的正确答案是4613732。

/*
 *             PROBLEM 2
 * Each new term in the Fibonacci sequence is generated by adding the previous two terms. 
 * By starting with 1 and 2, the first 10 terms will be:
 *
 * 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
 *
 * By considering the terms in the Fibonacci sequence whose values do not exceed four 
 * million, find the sum of the even-valued terms.
 */

public class problem2 
{
    public static void main(String args[])
    {
        int sum = 0;

        int[] anArray = new int[4000000];
        anArray[0] = 1;
        anArray[1] = 2;

        for (int i = 2; i <= anArray.length - 1; i++) {
            anArray[i] = anArray[i - 1] + anArray[i - 2];

            if (anArray[i] % 2 == 0 && anArray[i] <= 4000000) {
                sum += anArray[i];
            }
        }
        System.out.println(sum);        
    }
}
4

6 回答 6

1

您超出了int. 你计算的数字太多，最终得到负数。使数组的大小保持正常（例如 40），或者检查 if 语句以忽略负数。

实际上，只需将数组的大小更改为 40，因为 int 翻转后的任何内容都是错误的。

int [] anArray = new int[40];

另请注意，您没有添加2数组中的第二个数字。

当您的数字超过 4,000,000 时，您也可以跳出 for 循环，因为无论如何您都不关心它们。

于 2012-07-29T04:51:56.233 回答
1

首先，你错过了两个其次，为了避免溢出问题：http://en.wikipedia.org/wiki/Integer_overflow，一旦超过一百万，你应该插入一个 break 语句。

于 2012-07-29T04:59:25.573 回答
0

使用数组而不是为求和编写一些公式使得问题的解决非常普通。您可以简单地使用等于算术运算符，巧妙地避免使用数组。我的代码解决方案是这样的。希望它可以帮助你。

       /*PRoject euler problem2*/
       /*Sum of even terms in fibonacci sequence*/
           public class Euler2
             {

                static long fibosum()
                 {
                    long sum=0;
                    long initialint=0;
              long secondint=1;
              long fibo=initialint+secondint;
                while(fibo<4000000)
                  {
                    if(fibo%2==0)
                {
                  sum=sum+fibo;
                }
                         initialint=secondint;
                   secondint=fibo;
                   fibo=initialint+secondint;
                        }
             return sum;
               }
             public static void main(String args[])
              {
                 Euler2 a=new Euler2();
           System.out.println("Sum of even fibonacci numbers below 4000000 is"+a.fibosum());
               }
  }
于 2013-02-27T15:50:10.383 回答
0 
for(int i=2;i<=anArray.length-1;i++){
            anArray[i]=anArray[i-1]+anArray[i-2];

            if(anArray[i]%2==0 && anArray[i]<=4000000){
                    sum+=anArray[i];
            }
        }

您应该检查循环中斐波那契数的限制，而不仅仅是“总和”部分。因为你错过了支票，所以你溢出了。溢出后，数字“包装”回更小的数字，导致它们（可能，但绝对在这里）小于 4000000。

您可以在这里使用BigInteger来避免溢出。它没有很好的性能（至少对于 Java 1.6），但它可以解决这个问题。

于 2012-07-29T04:50:22.860 回答
0

逻辑在我看来是正确的，但这是一种低效的方法。Project Euler 旨在让您找出更好的算法，因此您的幼稚算法可能会耗尽时间或内存。

尝试在斐波那契数字中寻找模式以提出更快的方法。

编辑：我错过了你在达到 4000000 后没有跳出循环。在这种情况下，数字会溢出并给你不正确的结果。您需要在数字超过 4000000 后中断。此外，这个庞大的数组是完全没有必要的，因为您只需要最后两个数字来计算每个新数字。

于 2012-07-29T04:51:15.480 回答
-1

如果你观察斐波那契数列，每三个数都是偶数：

1,1, 2 ,3,5, 8 ,13,21, 34

所以一个长度为 3 的数组就足够了。我们可以生成接下来的 3 个斐波那契数并将其存储（覆盖）在数组中，数组中所有第三个元素（偶数 fib 数）的总和将为我们提供斐波那契数列中所有偶数的总和。

代码：

public class Prob2 {
    public static int sumOfEvenFibonacci(int limit){
        int fibonacci[] = {1, 1, 2}; 
        int j, sum = 2;

        while(fibonacci[2] < limit){
            for(j = 0; j < 3; j++){
                fibonacci[j] = fibonacci[(j+1)%3] + fibonacci[(j+2)%3];
            }
            sum += fibonacci[2];
        }
        return sum - fibonacci[2];
    }
}

琐碎的测试用例：

public class TestProb2 {

@Test
public void testSumOfMultiples(){
    int actual = Prob2.sumOfEvenFibonacci(15);
    assertEquals(10, actual);

    actual = Prob2.sumOfEvenFibonacci(50);
    assertEquals(44, actual);

    actual = Prob2.sumOfEvenFibonacci(200);
    assertEquals(188, actual);

    actual = Prob2.sumOfEvenFibonacci(4000000);
    assertEquals(4613732, actual);
}

}

PS：这个答案可能不完全回答OP的问题，但出于找到它的喜悦而想分享该技术。希望它可以帮助其他在这里寻找解决方案的人。

于 2014-07-08T13:01:21.893 回答