无限循环检测
Infinite loop detection
我想知道是否可以用基本的 java 知识来检测 and/or 停止无限循环。
我有一项学校任务(考虑到我们的编程知识处于基础水平),我们应该从用户那里获取输入 (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 等)
如果我们得到数字 1,我们应该打印 "number is lucky!",如果不是,它将陷入无限循环,我们应该打印 "number is not lucky!".
现在让我烦恼的是,如果它会陷入无限循环,他们如何期望我们打印 "number is not lucky"?
可能是编写和设计不当task/question还是实际上有一种基本知识水平的方法来检测和停止无限循环?
这是我的代码(w/o无限循环检测):
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;
}
}
}
总的来说,没有解决停机问题的方法。
但是,在您的特定情况下,我可以想出一种检测无限循环的方法。在每次迭代中,您计算一个数字(数字的平方和或前一个数字)。您可以将所有这些数字放在一个集合中。如果在某些迭代中你计算出一个已经在该集合中的数字,你就会知道你陷入了无限循环。
由于最大平方和是有界的(对于n位数的数字,最大位数的平方和是81*n),你要得到的不同值的数量相对较少你的迭代,所以如果你没有达到 1 并以成功结束,你将达到之前已经出现的值并报告失败。
虽然您无法提供通用的无限循环检测,但您可以为此用例提供一个简单的检测。你可以假设一旦你重复一个数字,你将永远循环下去,所以你需要做的就是检测一个重复的数字。
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.
在这种情况下,previous.add(sum)
将 return false
检测到重复项。
唯一的方法是设置最大迭代次数或超时算法
第一个问题 - 链条会延伸到无穷大吗?如果您有一个 n 位数字,那么下一个数字将小于 81 * n - 这是 999999 之后的下一个值。当 n>2 时,81n < 100n < 10^n,并且所有 n 位数字都小于大于 10^n。所以链是有界的,必须终止或重复。
第二个问题是如何检测环路。您可以存储所有访问过的值并检查它们。这在这种情况下可能是可行的,但通常它可能需要大量内存和时间来检查是否找到重复项。
一个更高效的算法在时间上和 space 可能是将在步骤 m/2 中找到的值存储在链中并将其与步骤 m 中的值进行比较。当您探索解决方案 space 时,您可以将其想象成在您身后拖着一根加长的绳子。最终(如果这是一个循环)您将遇到字符串的结尾。
也许你可以使用这样的东西:
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);
我想知道是否可以用基本的 java 知识来检测 and/or 停止无限循环。
我有一项学校任务(考虑到我们的编程知识处于基础水平),我们应该从用户那里获取输入 (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 等)
如果我们得到数字 1,我们应该打印 "number is lucky!",如果不是,它将陷入无限循环,我们应该打印 "number is not lucky!".
现在让我烦恼的是,如果它会陷入无限循环,他们如何期望我们打印 "number is not lucky"?
可能是编写和设计不当task/question还是实际上有一种基本知识水平的方法来检测和停止无限循环?
这是我的代码(w/o无限循环检测):
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;
}
}
}
总的来说,没有解决停机问题的方法。
但是,在您的特定情况下,我可以想出一种检测无限循环的方法。在每次迭代中,您计算一个数字(数字的平方和或前一个数字)。您可以将所有这些数字放在一个集合中。如果在某些迭代中你计算出一个已经在该集合中的数字,你就会知道你陷入了无限循环。
由于最大平方和是有界的(对于n位数的数字,最大位数的平方和是81*n),你要得到的不同值的数量相对较少你的迭代,所以如果你没有达到 1 并以成功结束,你将达到之前已经出现的值并报告失败。
虽然您无法提供通用的无限循环检测,但您可以为此用例提供一个简单的检测。你可以假设一旦你重复一个数字,你将永远循环下去,所以你需要做的就是检测一个重复的数字。
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.
在这种情况下,previous.add(sum)
将 return false
检测到重复项。
唯一的方法是设置最大迭代次数或超时算法
第一个问题 - 链条会延伸到无穷大吗?如果您有一个 n 位数字,那么下一个数字将小于 81 * n - 这是 999999 之后的下一个值。当 n>2 时,81n < 100n < 10^n,并且所有 n 位数字都小于大于 10^n。所以链是有界的,必须终止或重复。
第二个问题是如何检测环路。您可以存储所有访问过的值并检查它们。这在这种情况下可能是可行的,但通常它可能需要大量内存和时间来检查是否找到重复项。
一个更高效的算法在时间上和 space 可能是将在步骤 m/2 中找到的值存储在链中并将其与步骤 m 中的值进行比较。当您探索解决方案 space 时,您可以将其想象成在您身后拖着一根加长的绳子。最终(如果这是一个循环)您将遇到字符串的结尾。
也许你可以使用这样的东西:
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);