欧拉计划 #2 无穷大？

Question

我正在尝试解决Euler's Project #2，但我不断得到“Infinity”或“NaN”的答案（不是数字）我尝试将数字类型更改为 int （最初为 Double），但这并没有解决任何问题，只是给了我答案“-1833689714”

public class Pro {
    static int g = 1;
    static int n, f = 0;
    public static void main(String args[]) {
        for (int i = 0; i <= 4000000; i++) {
            f = f + g;
            g = f - g;
            if (f % 2 == 0) {
                n += f;
            }
        }
        System.out.println("Answer: " + n);
    }
}

问题是：

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

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

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

Answer 1

您的问题是整数溢出：在 Java 中，int 变量仅限于 Integer.MAX_VALUE (2147483647)。如果计算中超过此值，则会溢出到 Integer.MIN_VALUE，即最小的负值。请参阅：

public class IntegerOverflow {
    public static void main(String[] args) {
        int i = Integer.MAX_VALUE;
        System.out.println("i = Integer.MAX_VALUE: " + i);
        System.out.println("i + 1: " + (i + 1));
        System.out.println("i + 2: " + (i + 2));
    }
}

为了避免溢出问题，请使用 java.math.BigInteger 类：

import java.math.BigInteger;

public class BigIntegerExample {
    public static void main(String[] args) {
        BigInteger b = BigInteger.valueOf(Long.MAX_VALUE);
        System.out.println("b = Long.MAX_VALUE: " + b);
        System.out.println("b**2: " + b.multiply(b));
        System.out.println("b**3: " + b.pow(3));
        System.out.println("b**10: " + b.pow(10));
    }
}

---

注意：因为您没有要求帮助解决问题本身，我只是回答问题。希望这有帮助

Answer 2

您可能遇到溢出。 fibo(4000000) 远高于 MAX_INT。

注意：并不是要求您求前 4,000,000 个数字中的偶数之和，而是求其值不超过 4,000,000 的偶数元素之和。

您应该检查是否 f< 4000000 如果不是，则中断，而不是等待 i 达到 4,000,000

Answer 3

您正在检查前 400 万个斐波那契数，您只需检查项，直到斐波那契数项大于 400 万个，然后停止。您得到负数的原因是您最终得到的斐波那契项大于 Integer.MAX_INT，此时您会溢出并开始得到负数，并将其添加到总数中。如果您不确定最终答案是否会超过 Integer.MAX_INT，则应该使用 long 作为累加器而不是 int。

Answer 4

使用 GMP 处理 C 中的大数。
之前稍微思考一下也没有什么坏处（比如奇数与偶数的出现频率，斐波那契数列的前 n 个元素的总和是多少）...

Answer 5

您可以使用long 代替int。

每三个表达式都是偶数，因此您只需计算每三个值。这稍微快一些，因为它循环的次数更少，并且您不必测试偶数/奇数。

您只需n 而不是小于400 万的i。

Answer 6

这就是我得到答案的方式：

def fib():
        x,y = 0,1
        while True:
            yield x
            x,y = y, x+y

def even(seq):
    for number in seq:
        if not number % 2:
            yield number

def under_a_million(seq):
    for number in seq:
        if number > 4000000:
            break
        yield number   

print sum(even(under_a_million(fib())))

-M1K3

Answer 7

您正在考虑斐波那契数列的前 4,000,000 项，而不是不超过 4,000,000 项的前 x 项。