欧拉计划 14 Java

Question

我在 Problem 14 on Project Euler 上遇到了问题。我不明白为什么我的代码 (Java) 不起作用，如有任何帮助，我们将不胜感激。

public class Calculate {

    public static void main(String[] args){
        System.out.println(calc());
    }

    public static int calc(){
        int max = 0;
        int maxI = 0;
        for (int i = 0; i < 1000000; i++){
            if (seqLen(i) >= max){
                max = seqLen(i);
                maxI = i;
            }
        }
        return maxI;
    }

    public static int seqLen(int seed){
        if (seed <= 0) return 0;
        if (seed == 1) return 1;
        int len = 1;
        if (seed % 2 == 0){
            len += seqLen(seed/2);
        }
        else{
            len += seqLen((3*seed)+1);
        }
        return len;
    }

}

谢谢！

Answer 1

您运行因 int 变量而溢出。

此计算中出现的最大数量（使用强力方法时）是 56991483520。

Java的int最大值是2^31-1 == 2147483647，明显偏小

因此请更改您的变量等以使用 long。这里的最大值是 2^63-1 == 9223372036854775807，这将适合所有值。

Answer 2

您正在突破 int 限制。

使用long:

public static long calc() {
    long max = 0;
    long maxI = 0;
    for (long i = 0; i < 1000000; i++) {
        long len = seqLen(i);
        if (len >= max) {
            max = len;
            maxI = i;
        }
    }
    return maxI;
}

public static long seqLen(long seed) {
    if (seed <= 0) {
        return 0;
    }
    if (seed == 1) {
        return 1;
    }
    long len = 1;
    if (seed % 2 == 0) {
        len += seqLen(seed / 2);
    } else {
        len += seqLen((3 * seed) + 1);
    }
    return len;
}

public void test() {
    System.out.println(seqLen(13));
    System.out.println(calc());
}

为您提供 837799 的正确结果。

请注意，有 better/more 个比这个更有效的算法。

Answer 3

实际上，您不必检查从 1 到 499999。你只需要检查从 500000 到 999999 因为下一步是 500000 到 999999 之间的任何偶数将是从 1 到 499999 的某个整数。这意味着 1 到 499999 之间的整数不能作为答案。

所以把for循环改成下面这样

for (int i = 500000; i < 1000000; i++) {

}

而且"i"不必很长而 "seed" 必须很长。

欧拉计划 14 Java

Project Euler 14 Java

java

recursion

collatz