java - Project Euler 14 Java

Question

I have been having trouble on Problem 14 on Project Euler. I don't understand why my code(Java) isn't working and any help would be appreciated.

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;
    }

}

Thanks!

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。

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

Answer 3

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

所以将for循环更改为以下

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

}

并且“i”不必很长，而“seed”必须很长。