java 无限循环检测

Infinite loop detection

提问by SadCoffeeBean

I wonder if it is possible to detect and/or stop infinite loop with basic java knowledge.

我想知道是否可以使用基本的 Java 知识检测和/或停止无限循环。

I got a school task(which considers our programming knowledge is on basic level) where we should take an input (int) from user and then take the sum of squares of the digits of that number (i.e. 123-->1^2+2^2+3^2). Then that result should be put in a while loop and it should repeat the same thing until it reaches 1 (i.e. 123-->1^2+2^2+3^2=14-->1^2+4^2=17-->1^2+7^2 etc)

我有一个学校任务（它认为我们的编程知识处于基本水平），我们应该从用户那里获取输入（int），然后获取该数字的数字的平方和（即 123-->1^2+ 2^2+3^2）。然后该结果应该放在一个while循环中，它应该重复同样的事情，直到达到1（即123-->1^2+2^2+3^2=14-->1^2+4^2 =17-->1^2+7^2 等）

If we get number 1 we should print "number is lucky!" and if it isn't it will be stuck in an infinite loop and we should print "number is not lucky!".

如果我们得到数字 1，我们应该打印“数字是幸运的！” 如果不是，它将陷入无限循环，我们应该打印“数字不幸运！”。

Now whats bugging me is how do they expect us to print "number is not lucky" if it will be stuck in an infinite loop ?

现在困扰我的是，如果它会陷入无限循环，他们如何期望我们打印“数字不幸运”？

Is it possibly the badly written and designed task/question or there actually is a basic-level-knowledge way to detect and stop an infinite loop?

是否可能是编写和设计不当的任务/问题，或者实际上有一种基本级别的知识方法来检测和停止无限循环？

---

---

Here is my code(w/o the infinite loop detection):

这是我的代码（没有无限循环检测）：

import java.util.Scanner;

public class Vezba {

public static void main(String[] args) {
    boolean run = true;
    Scanner sc = new Scanner(System.in);
    int number = sc.nextInt();
    int digits;
    int sum=0;
    int k = 10;
    int j = 1;
    while(run){
        if(number<0){
            run=false;
        }
        int len = String.valueOf(number).length();
       /* Takes out each digit to make the first sum (probably redundant but please ignore)*/
        while(len>0){
            digits = number%k/j;
            j*=10;
            k*=10;
            len--;
            sum += digits*digits;
        }
       /* Repeats the process until sum is 1*/
        while(sum>1){
            int len2 = String.valueOf(sum).length();
            int pom = 1;
            int k1=10;
            while(len2>0){
                digits = sum%k1/pom;
                pom*=10;
                k1*=10;
                len2--;
                sum += digits*digits;
            }
        }
        System.out.println("Number is lucky!");
        run=false;
    }
}  
}

---

---

采纳答案by Eran

In general, there is no solution to the Halting problem.

一般来说，没有解决停机问题的方法。

However, in your specific case I can think of a way to detect an infinite loop. In each iteration you calculate a number (the sum of the squares of the digits or the previous number). You can put all those numbers in a Set. If in some iteration you calculate a number that is already in that Set, you know that you are stuck in an infinite loop.

但是，在您的特定情况下，我可以想到一种检测无限循环的方法。在每次迭代中，您计算​​一个数字（数字或前一个数字的平方和）。你可以把所有这些数字放在一个集合中。如果在某些迭代中您计算出该集合中已有的数字，则您知道自己陷入了无限循环。

Since the largest sum of squares is bound (for a number with n digits, the largest sum of squares of the digits is 81*n), there is a relatively small number of distinct values you are going to get in your iterations, so if you don't reach 1 and end with a success, you'll reach a value that's already appeared before and report a failure.

由于最大平方和是有界的（对于具有 n 个数字的数字，数字的最大平方和为 81*n），因此您将在迭代中获得的不同值的数量相对较少，因此如果您没有达到 1 并以成功结束，您将达到之前已经出现的值并报告失败。

回答by Peter Lawrey

While you can't provide a generic infinite loop detection, you can provide a simple one for this use case. You can make the assumption that once you repeat a number, you will always loop forever, so all you need to do is detect a repeated number.

虽然您无法提供通用的无限循环检测，但您可以为此用例提供一个简单的检测。你可以假设一旦你重复一个数字，你将永远循环，所以你需要做的就是检测一个重复的数字。

Set<Integer> previous = new HashSet<>();

// in you loop
int sum, number;
do {
   sum = 0;
   int len = String.valueOf(number).length();
   /* Takes out each digit to make the first sum (probably redundant but please ignore)*/
    while(len>0){
        digits = number%k/j;
        j*=10;
        k*=10;
        len--;
        sum += digits*digits;
    }
} while (sum > 1 && previous.add(sum))
if (sum > 1) // no lucky.

In this case, previous.add(sum)will return falseis a duplicate is detected.

在这种情况下，previous.add(sum)将返回false检测到重复项。

回答by fantarama

The only way is to set a max iterations number or a timeout algorithm

唯一的方法是设置最大迭代次数或超时算法

回答by Neil Masson

First question - will the chain stretch to infinity? If you have an n-digit number, then the next number will be less than 81 * n - which is the next value after 999999.. 81n < 100n < 10^n when n>2, and all n-digit numbers are less than 10^n. So chains are bounded and must either terminate or repeat.

第一个问题 - 链条会延伸到无穷大吗？如果你有一个 n 位数字，那么下一个数字将小于 81 * n - 这是 999999 之后的下一个值.. 81n < 100n < 10^n 当 n>2 时，所有 n 位数字都小于超过 10^n。所以链是有界的，必须终止或重复。

Second question is how to detect a loop. You could store all visited values and check against them. This is probably feasible in this case, but in general it can require a large amount of memory and time to check if a duplicate is found.

第二个问题是如何检测循环。您可以存储所有访问过的值并检查它们。在这种情况下这可能是可行的，但通常需要大量内存和时间来检查是否找到重复项。

A more efficient algorithm in time and space may be to store the value found at step m/2 in the chain and compare it to the one at step m. You can think of this as trailing a lengthening piece of string behind you as you explore the solution space. Eventually (if this a loop) you will encounter the end of your string.

一种更有效的时间和空间算法可能是将在第 m/2 步找到的值存储在链中，并将其与第 m 步的值进行比较。您可以将其视为在探索解决方案空间时在身后拖着一根拉长的绳子。最终（如果这是一个循环）您将遇到字符串的结尾。

回答by Arya Gohad

Maybe you can use something like this:

也许你可以使用这样的东西：

n = in.nextInt();
int t = n;
while (n != 0)
{
    r = n % 10;
    s += Math.pow(r, 2);
    n /= 10;
}
if (s == t)
System.out.println(whatever is given);
else
System.out.println (whatever is given);