Java中euler项目#14的运行时间太长

Question

我的Euler Project 14代码如下.我已经运行此代码超过3个小时的输出结果,它似乎是无限的.当我测试单个数字(如11,27)时,它将快速输出collat​​z链数:14和111.但我不知道为什么它不能输出1000000数字的最大链数.

/*Problem 14
 * 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.
 */
package number;  
public class LongestCollatzSequence {
    public static int collatzNum(int n){
        int count = 0;
        while(n != 1){
            if(n%2 == 0)
                n = n/2;
            else 
                n = 3*n + 1;
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        int max = 0;
        for(int i = 10; i <= 1000000; i++){
            if(collatzNum(i) > collatzNum(max))
                max = i;
        }
        System.out.println(max);
    }
}

此外,我转for(int i = 10; i <= 1000000; i++)来for(int i = 10; i <= 10; i++),数字仍在运行,而不输出所有的时间这么短名单.我的代码出了什么问题？

这是另一个人的决议,rianjs.net的代码是:

public class Problem014
{
    public static void main(String[] args)
    {
        long begin = System.currentTimeMillis();
        LinkedList<Long> list = new LinkedList<Long>();
        long length = 0;
        int res = 0;
        for(int j = 10; j < 1000000; j++){
            long i = j;
            while (i != 1){
                if (i % 2 == 0){
                    i /= 2;
                    list.add(i);
                }
                else{
                    i = (3 * i) + 1;
                    list.add(i);
                }
            }
            if(list.size() > length){
                length = list.size();
                res = j;
            }
            list.clear();
        }
        long end = System.currentTimeMillis();
        System.out.println(res+" with chain size: "+ length);
        System.out.println(end-begin + "ms");
    }
}

他的代码运行良好,我想知道为什么我的代码无法获得输出以及两个分辨率的差异是什么？

Answer 1

这个论点int n你的collatzNum功能将溢出的值113383.正如你所看到的,其他的实现使用的临时值长变量.

除此之外,您可以通过不计算collatzNum(max)每个循环迭代来优化代码,但仅当max实际更改时,在这种情况下,您已经将new collatzNum(max)作为返回值collatzNum(i).