某个输入参数之上的突然无限循环？

Question

在学习Java时，我正在重新处理一些Project问题。这是关于问题14最长的Collatz序列：https://projecteuler.net/problem=14

我的程序在像1000这样的较低的CEILING上运行得很好，但是当像posted那样执行时，我想是无限循环的吗？这里出了什么问题？

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(collatzLength(1000000));工作得很好，所以我认为我们可以在这里排除错误。

Answer 1

您应该使用long而不是int。int在用collatzLength进行计算时溢出，这将导致无限循环。从问题描述：

注:一旦链开始，条款允许超过100万。

引起问题的数字: 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;
    }
}