java - 在某些输入参数之上突然无限循环？

Question

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

我的程序在较低的 CEILING(例如 1000)下运行得很好，但我认为当它像发布的那样执行时会无限循环，对吗？这里出了什么问题？

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