java - 某个输入参数之上突然出现无限循环？

Question

在学习 Java 时，我正在重做一些 Project Euler 问题。 这是关于问题 14 - 最长的 Collat​​z 序列:https://projecteuler.net/problem=14

我的程序在 1000 等较低的 CEILING 下运行得很好，但是当像发布一样执行时，它会无限循环，我想？这里出了什么问题？

public class Test {
    public static void main(String[] args) {
        int tempMax = 0;
        final int CEILING = 1_000_000;

        for (int j = 1; j < CEILING; ++j) {
            tempMax = Math.max(tempMax, collatzLength(j));
        }
        System.out.println(tempMax);
    }

    static int collatzLength(int n) { //computes length of collatz-sequence starting with n
            int temp = n;

            for (int length = 1; ; ++length) {
                if (temp == 1) 
                    return length;
                else if (temp % 2 == 0)
                    temp /= 2;
                else
                    temp = temp * 3 + 1;
            }
    }
}

单独调用System.out.println(collat​​zLength(1000000));工作得很好，所以我认为我们可以在这里排除错误。

Answer 1

您应该使用long 而不是int。在 collat​​zLength 中进行计算时，int 溢出，从而导致无限循环。从问题描述来看:

NOTE: Once the chain starts the terms are allowed to go above one million.

导致问题的号码:113383

long 版本给出的结果仍然不正确，因为您正在打印最长链的长度，但您需要产生最长链的数字。

public static void main(String[] args)
{
    int tempMax = 0;
    final int CEILING = 1_000_000;

    for (int j = 1; j < CEILING; ++j)
    {
        tempMax = Math.max(tempMax, collatzLength(j));
    }
    System.out.println(tempMax);
}

static int collatzLength(long n)
{
    long temp = n;

    for (int length = 1;; ++length)
    {
        if (temp == 1)
            return length;
        else if (temp % 2 == 0)
            temp /= 2;
        else
            temp = temp * 3 + 1;
    }
}