java用递归再次尝试了Euler的#14，但对我不起作用。扰流器

Question

我早些时候发过帖子，试图对它施加暴力，但没用。下面是我对递归的尝试#2（第一次使用递归方法）。请帮忙

结果如下：代码运行良好，数字较小，但当我们达到100万时，代码就会运行，而不会发生任何事情。在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);
    }
}

Answer 2

主要的问题是，你正试图用ints对大数进行数学运算。当你的程序陷入desiredMax的999167时，你将进入一个无限循环

在Java中，int可以表示的最大值是2,147,483,647。 当你的算法达到999167时，它很快就会超过这个限制。 如果在内部while循环中打印currentNumber的值，您会看到：

...
1330496806
665248403
1995745210
997872605
-1301349480    <  oops
-650674740
-325337370
...

您正在尝试将currentNumber设置为2,993,617,816，因此您的值将设置为overflow

这会导致你的while循环永远不会终止，因为你不会考虑负数。你很快就适应了一系列重复的

-25
-74
-37
-110
-55
-164
-82
-41
-122
-61
-182
-91
-272
-136
-68
-34
-17
-50
-25
... ad infinitum

您可以尝试切换到更大的数值表示（long），但是，即使切换到使用long值，您尝试递归的方式也会导致堆栈溢出long，在您完成对1000000的计算之前。（在我的盒子上，当我开始997474时，我得到一个StackOverflowError）

你需要回去重新思考你的课程结构。递归可能是一个有用的工具，但使用它是危险的，除非你知道你不会走得太深

Answer 3

这是一个可以使用Memoization的好例子

下面是一个使用递归的解决方案，但它避免了不断重复已经计算过的路径

这也将链计算代码与搜索最大代码分离

public class Euler14 {
    static long[]   records = new long[1000000];

    // //////////////////////////////////////////////
    // Recursively calculates one chain length
    //
    static long getLength(long n) {
        // Terminating condition
        if (n == 1) {
            return n;
        }
        // Have we already calculated this?
        if ((n < records.length) && (records[(int) n] != 0)) {
            return records[(int) n];
        }
        // Haven't calculated this yet, so calculate it now
        long length = getLength(n % 2 == 0 ? n / 2 : 3 * n + 1) + 1;
        // Record the result for later use
        if (n < records.length) {
            records[(int) n] = length;
        }
        return length;
    }

    static long calculateQuestionFourteen() {
        long maxLength = 0;
        long maxStart = 0;
        for (long i = 1; i < 1000000; ++i) {
            long thisLength = getLength(i);
            if (thisLength > maxLength) {
                maxLength = thisLength;
                maxStart = i;
            }
        }
        return maxStart;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(calculateQuestionFourteen());
        System.out.println(System.currentTimeMillis() - start);
    }
}