Java循环次数有限制吗?

huangapple go评论75阅读模式
英文:

Does Java have a limit on loop cycles?

问题

我在Java中解决了Project Euler问题#14(https://projecteuler.net/problem=14),但当我在PowerShell中运行它时,它每次在i = 113383时停止迭代。我用Python重写了解决方案,虽然速度较慢,但运行得非常正常。根据我(完全相同)的Python解决方案,答案是产生最长链的数字为837799,链长为524次操作。

为什么Java解决方案无法完成for循环?在Java中是否有某种限制,决定了它可以在循环中停留的时间有多长?我找不到其他解释。以下是Java代码。我在那里写了System.out.println(i),以便查看正在发生的情况。

class ProjectEuler14 {

	public static void main(String[] args) {

		int largestNumber = 1;
		int largestChain = 1;
		int currentNumber;
		int chainLength;

		for (int i = 2; i < 1000000; i++) {
			System.out.println(i);
			currentNumber = i;
			chainLength = 0;

			while (currentNumber != 1) {
				if (currentNumber % 2 == 0) currentNumber /= 2;
				else currentNumber = 3 * currentNumber + 1;
				chainLength++;
			}

			if (chainLength > largestChain) {
				largestChain = chainLength;
				largestNumber = i;
			}

		}

		System.out.println("\n\nThe number under million that produces the "
						   + "longest chain is " + largestNumber +
						   " and the chain's length is " + largestChain);
	}
}
英文:

I solved the Project Euler problem #14 https://projecteuler.net/problem=14 on Java, but when I run it in Powershell, it stops iterating at exactly i = 113383 every time. I rewrote the solution on python, and it works perfectly fine, albeit slowly. According to my (identical) python solution, the answer is that the number that produces the longest chain is 837799 and the chain is 524 operations long.

Why does the Java solution not finish the for-loop? Is there some kind of limit in Java on how long it can stay in a loop? I cannot come up with any other explanation. Java code below. I wrote the System.out.println(i) there just to see what is going on.

class ProjectEuler14 {

	public static void main(String[] args) {

		int largestNumber = 1;
		int largestChain = 1;
		int currentNumber;
		int chainLength;

		for (int i = 2; i &lt; 1000000; i++) {
			System.out.println(i);
			currentNumber = i;
			chainLength = 0;

			while (currentNumber != 1) {
				if (currentNumber % 2 == 0) currentNumber /= 2;
				else currentNumber = 3 * currentNumber + 1;
				chainLength++;
			}

			if (chainLength &gt; largestChain) {
				largestChain = chainLength;
				largestNumber = i;
			}

		}

		System.out.println(&quot;\n\nThe number under million that produces the &quot;
						   + &quot;longest chain is &quot; + largestNumber +
						   &quot; and the chain&#39;s length is &quot; + largestChain);
	}
}

答案1

得分: 3

这不是for循环,而是while循环。条件currentNumber != 1始终为真,永远不会结束。

在Java中,int被明确定义为在-2^31+2^31 -1之间的整数,包括这两个值,并且操作会"回绕"。试一下吧!

int x = 2^31 -1;
x++;
System.out.println(x);

这会打印出一个很大的负数(确切地说是-2^31)。

这就是你的算法中发生的情况,这就是为什么它永远不会结束的原因。

一个简单的解决方法是将类型升级为long;它们同样快速,因为现在有64位处理器!并且使用64位,因此它们的范围是-2^63+2^63-1

Python会悄悄地将其数字扩展到较慢的范围,而Java则会做出不同的选择(对于加密和其他用途,实际上是期望发生回绕的)。

如果想走得更远,您始终可以使用BigInteger,它会根据需要不断增长(随着增长会变得更慢并且占用更多内存)。

要知道发生了回绕,3倍操作将导致一个比原来小的数字,您可以检查这一点:

替换:

else currentNumber = 3 * currentNumber + 1;

为:

else {
    int newNumber = currentNumber * 3 + 1;
    if (newNumber < currentNumber) throw new IllegalStateException("Overflow has occurred; 3 * " + currentNumber + " + 1 exceeds ints capacities.");
    currentNumber = newNumber;
}

然后重新运行它。您将看到您的应用程序会很好地解释自己。

英文:

It's not the for loop. It's the while loop. The condition currentNumber != 1 is always true; forever.

In java, an int is specifically defined as an integral number between -2^31 and +2^31 -1, inclusive, and operations 'roll over'. try it!

int x = 2^31 -1;
x++;
System.out.println(x);

this prints a large negative number (in fact, precisely -2^31).

It's happening in your algorithm, and that's why it never finishes.

A trivial solution is to 'upgrade' to longs; they are just as fast, really (yay 64-bit processors!) and use 64 bits, thus giving them a range of -2^63 to +2^63-1.

Python sort of scales up its numbers into slowness silently, java makes different choices (and, for crypto and other purposes, that rollover thing is in fact desired).

If you want to go even further, you can always use BigInteger, which grows as much as you need forever (becoming slower and taking more memory as it goes).

To know rollover occurred, the 3* operation would then result in a number that is lower than the original, and you can check for that:

replace:

else currentNumber = 3 * currentNumber + 1;

with:

else {
    int newNumber = currentNumber * 3 + 1;
    if (newNumber &lt; currentNumber) throw new IllegalStateException(&quot;Overflow has occurred; 3 * &quot; + currentNumber + &quot; + 1 exceeds ints capacities.&quot;);
    currentNumber = newNumber;
}

and rerun it. You'll see your app nicely explain itself.

答案2

得分: 1

currentNumber超过了int的大小限制,请改用long。

英文:

The currentNumber is exceeding size of int, use long instead.

答案3

得分: 0

你有溢出整数的问题吗?
将 int 改为 long。

long largestNumber = 1;
long largestChain = 1;
long currentNumber;
long chainLength;

for (int i = 2; i < 1000000; i++) {
    //System.out.println(i);
    currentNumber = i;
    chainLength = 0;

    while (currentNumber != 1) {

        //System.out.println("& = " + currentNumber);
        if (currentNumber % 2 == 0) {
            currentNumber /= 2;
        } else {
            currentNumber = (3 * currentNumber) + 1;
        }
        chainLength++;

    }

    // System.out.println("################################ " + i);
    if (chainLength > largestChain) {
        largestChain = chainLength;
        largestNumber = i;
    }

}

System.out.println("\n\nThe number under million that produces the "
        + "longest chain is " + largestNumber
        + " and the chain's length is " + largestChain);
英文:

Do you hava problem overflow int.
Change int to long.

        long largestNumber = 1;
        long largestChain = 1;
        long currentNumber;
        long chainLength;

        for (int i = 2; i &lt; 1000000; i++) {
            //System.out.println(i);
            currentNumber = i;
            chainLength = 0;

            while (currentNumber != 1) {
               
                //System.out.println(&quot;# = &quot; + currentNumber);
                if (currentNumber % 2 == 0) {
                    currentNumber /= 2;
                } else {
                    currentNumber = (3 * currentNumber) +1 ;
                }
                chainLength++;
                
                 

            }

           // System.out.println(&quot;################################ &quot; + i);
            if (chainLength &gt; largestChain) {
                largestChain = chainLength;
                largestNumber = i;
            }

        }

        System.out.println(&quot;\n\nThe number under million that produces the &quot;
                + &quot;longest chain is &quot; + largestNumber
                + &quot; and the chain&#39;s length is &quot; + largestChain);

huangapple
  • 本文由 发表于 2020年7月24日 00:35:26
  • 转载请务必保留本文链接:https://go.coder-hub.com/63059034.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定