欧拉计划第14题 Java实现

Question

我在欧拉计划的第14个问题上遇到了困难。我不明白为什么我的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;
    }

}

谢谢！

- monsterbananas

---

你看到错误了吗？它在做什么？ - mmmmmpie

我的猜测是int变量溢出了。 - Sirko

它在一系列476个中产生了910107。 - monsterbananas

请查看此链接 https://interviewquizandanswers.blogspot.com/2020/04/project-euler-14-longest-collatz.html。 - dasunse

Answer 1

你的int变量溢出了。

在这个计算中出现的最大数字（使用暴力方法）为56991483520。

Java的int最大值是2^31-1 == 2147483647，很明显比这个小。

所以将你的变量等改成使用long类型。在这里，最大值是2^63-1 == 9223372036854775807，适用于所有值。

- Sirko

---

谢谢！我忘记它会变得那么大，我只看了长度。 - monsterbananas

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的正确结果。

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

- OldCurmudgeon

---

谢谢！你能告诉我它在哪里超出了整数限制吗？因为这些数字对我来说似乎不是很大。 - monsterbananas

我认为提供Project Euler的最终答案不是一个好主意，-) - Sirko

@monsterbananas - Sirko在他的回答中提到了这一点。 - OldCurmudgeon

@Sirko - 我不会称这为最终答案 - 它甚至不是一个特别好的解决方案。我希望 OP 被鼓励去改进它 - 在许多语言中，这个问题有很多解决方案。 - OldCurmudgeon

@OldCurmudgeon 我只是指的是以“这将为您提供正确的结果…”开头的那一行。原帖作者至少应该能够自己运行代码。 - Sirko

Answer 3

其实，您不必从1到499999进行检查。 您只需要从500000到999999进行检查， 因为在500000和999999之间的任何偶数的下一步 都将是来自1到499999的某个整数。 这意味着1到499999之间的整数不能是答案。

因此，请将for循环更改为以下内容

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

}

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

- Soonil Hong