欧拉项目＃14在Java中时间过长运行 [英] Too long runtime of euler project #14 in Java

问题描述

我的$ C $欧拉项目14 c是如下。我已经运行此code超过3小时，输出的结果，这似乎是无穷的。当我测试单个数字，如11，27，它将输出在Collat​​z链号码：14和111迅速。但我不知道为什么它不能输出百万数量的最大链数量。

My code of Euler Project 14 is below. I have run this code for more than 3 hours with output result and it seems to be infinite. When I test a single number such as 11, 27, it will output the collatz chain number:14 and 111 quickly. But I don't know why it couldn't output 1000000 number's max chain number.

/*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＆LT; = 1000000;我++）到的for（int i = 10;我＆LT; = 10;我++），数字这样的短名单，仍在运行的所有时间无输出。有什么毛病我的code？

Furthermore, I turn for(int i = 10; i <= 1000000; i++) to for(int i = 10; i <= 10; i++), such a short list of numbers, it is still running all the time without output. What's wrong with my code?

下面是另一个人的分辨率， rianjs.net 的code是：

Here is another person's resolution, rianjs.net the code is :

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

他的code运行良好，我想知道为什么我的code不能得到的输出，是什么让这两个分辨率的差异？

His code runs well, I want to know why my code cannot get the output and what makes the difference of the two resolution?

推荐答案

参数 INTñ你的 collat​​zNum 功能将溢出的值113383.正如你所看到的，其他实现使用一个长变量为临时值。

The argument int n of your collatzNum function will overflow for the value 113383. As you can see, the other implementation uses a long variable for the temporary value.

除此之外，您可以通过不计算优化codeA很多 collat​​zNum（最大）为每个循环迭代，但只有当最大实际的变化，这种情况下，你已经有了新的 collat​​zNum（最大）从一个返回值 collat​​zNum（我）。

In addition to that, you can optimize your code a lot by not calculation collatzNum(max) for each loop iteration, but only when max actually changes, in which case you already have the new collatzNum(max)as a return value from collatzNum(i).

这篇关于欧拉项目＃14在Java中时间过长运行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！