我正在尝试解决这个问题,这不是家庭作业问题,它只是我提交给 uva.onlinejudge.org 的代码,这样我就可以通过示例更好地学习 Java。这是问题示例输入:
3 100
34 100
75 250
27 2147483647
101 304
101 303
-1 -1
这是简单的输出:
Case 1: A = 3, limit = 100, number of terms = 8
Case 2: A = 34, limit = 100, number of terms = 14
Case 3: A = 75, limit = 250, number of terms = 3
Case 4: A = 27, limit = 2147483647, number of terms = 112
Case 5: A = 101, limit = 304, number of terms = 26
Case 6: A = 101, limit = 303, number of terms = 1
问题是这必须在 3 秒的时间间隔内执行,否则你的问题将不会被接受为解决方案,这里是我到目前为止提出的,它的工作应该只是执行时间不在 3 秒内秒,这是代码:
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner stdin = new Scanner(System.in);
int start;
int limit;
int terms;
int a = 0;
while (stdin.hasNext()) {
start = stdin.nextInt();
limit = stdin.nextInt();
if (start > 0) {
terms = getLength(start, limit);
a++;
} else {
break;
}
System.out.println("Case "+a+": A = "+start+", limit = "+limit+", number of terms = "+terms);
}
}
public static int getLength(int x, int y) {
int length = 1;
while (x != 1) {
if (x <= y) {
if ( x % 2 == 0) {
x = x / 2;
length++;
}else{
x = x * 3 + 1;
length++;
}
} else {
length--;
break;
}
}
return length;
}
}
是的,这就是解决问题的方式:
Lothar Collatz 给出的算法生成整数序列,描述如下:
Step 1:
Choose an arbitrary positive integer A as the first item in the sequence.
Step 2:
If A = 1 then stop.
Step 3:
If A is even, then replace A by A / 2 and go to step 2.
Step 4:
If A is odd, then replace A by 3 * A + 1 and go to step 2.
是的,我的问题是如何让它在 3 秒的时间间隔内工作?
最佳答案
我通过谷歌搜索找到了this thread其他几个人遇到了同样的问题,解决方案是使用 64 位算法而不是 32 位算法。
尝试将 int
更改为 long
,看看是否有帮助。
关于java - Collatz 序列问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2578559/