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

Question

在学习 Java 的同时，我正在重做一些 Project Euler 问题。这是关于问题 14 - 最长的 Collatz 序列：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(collatzLength(1000000)); 效果很好，所以我认为我们可以排除这里的错误。

Answer 1

您应该使用 long 而不是 int。在 collatzLength 中进行计算时 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;
    }
}

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

Sudden infinite loop above certain input argument?

java

integer-overflow

infinite-loop