java - 再次用递归尝试了欧拉的#14，对我来说不起作用。剧透 欧拉 14 号

Question

我之前曾尝试暴力破解它，但没有成功。这是我的递归尝试#2(第一次使用递归方法)。请帮忙!

发生的情况是这样的:代码运行良好，数字较小，但是当我们达到一百万时，代码就会运行，并且什么也不会发生。在 Eclipse 中，它仍然为我提供了结束的选项，但我已经让它运行了很长一段时间而没有任何帮助。

/**
* The following iterative sequence is defined for the set of positive
* integers:
*
* n → n/2 (n is even) n → 3n + 1 (n is odd)
*
* Using the rule above and starting with 13, we generate the following
* sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
*
* It can be seen that this sequence (starting at 13 and finishing at 1)
* contains 10 terms. Although it has not been proved yet (Collatz Problem),
* it is thought that all starting numbers finish at 1.
*
* Which starting number, under one million, produces the longest chain?
*
* NOTE: Once the chain starts the terms are allowed to go above one
* million.
*/
public class Euler14 {
    static int desiredMax = 1000000;
    static int maxTerm = 0;
    static int maxNumberOfTerms = 0;
    static int currentNumber = 0;
    static int numberOfTerms = 0;
    public static void doMath(int startingNumber) {
        if(startingNumber == 1) {
            System.out.print( maxTerm + " " + maxNumberOfTerms);
        }
        else {
            currentNumber = desiredMax;
            while(currentNumber!= 1) {
                if(currentNumber%2 == 0) {
                    currentNumber = currentNumber/2;
                    numberOfTerms++;
                } else {
                    currentNumber = (3 * currentNumber) + 1;
                    numberOfTerms++;
                }
            }
            numberOfTerms++;
            if(numberOfTerms > maxNumberOfTerms) {
                maxNumberOfTerms = numberOfTerms;
                maxTerm = startingNumber;
            }
            desiredMax--;
            doMath(desiredMax);

        }
    }
    public static void main(String[] args) {

        doMath(desiredMax);
    }

}

Answer 1

您的代码有很多错误:

• 使用递归方法，该方法相当于向下循环
• 使用静态变量
• numberOfTerms 从未重新初始化
• 正如 azurefrog 所指出的，您有一个整数溢出，这导致了无限循环。

当他想出答案时，我正在重新排列你的代码，并进行尽可能少的更改，所以我现在所能做的就是向你展示一个与你的代码非常相似的工作代码。看看这样有多干净:

public class Euler14 {
    public static void main(String[] args) {
        int maxTerm = 1000000;
        int maxNumberOfTerms = 1;

        // this loop replaces your recursion, which is not needed here and quite costly even if it is tail-recursion
        for (int i = maxTerm ; i >= 2; i--) {
            int numberOfTerms = 0;
            // declare as long to prevent the overflow
            long currentNumber = i;
            while (currentNumber != 1) {
                if (currentNumber % 2 == 0)
                    currentNumber = currentNumber / 2;
                else
                    currentNumber = (3 * currentNumber) + 1;

                numberOfTerms++;
                if (numberOfTerms > maxNumberOfTerms) {
                    maxNumberOfTerms = numberOfTerms;
                    maxTerm = i;
                }
            }
        }
        System.out.println(maxTerm);
    }
}