在试图找到阶乘 val
的最后一位的 Main
类中,为什么
public static void main(String[] args) {
int testcases = sc.nextInt();
for (int i = 0; i < testcases; i++) {
int result = 0;
int val = sc.nextInt();
if (val < 3) {
result = val;
} else {
for (int j = 1; j <= val; j--) {
result *= j;
result %= 10;
}
}
System.out.println(result);
}
}
除了此代码段中的差异外,计算时间比相同代码长得多:
for (int j = 1; j <= val; j++) {
result *= j;
result %= 10;
}
我知道第二次迭代没有提供正确的答案,但我很好奇为什么计算第二次而不是第一次循环需要这么长的时间。
最佳答案
循环代码在做什么
For 循环根据 3 个条件多次运行一段代码:
- 循环变量的起始值(在你的例子中是
int j = 1
) - 循环继续的条件(在您的情况下为
j <= val
- 因此一旦j
变得大于或等于 val,它将停止 - 循环变量随每次迭代而变化的方式(在您的情况下为
j--
或j++
j--
是减量运算符。与 j = j - 1
相同. j++
另一方面是增量运算符。与 j = j + 1
相同
这意味着循环for (int j = 1; j <= val; j--)
将使用 j = 1
运行代码块然后递减 j
的值.只要 j
就会这样做小于或等于 val
.另一方面,循环 for (int j = 1; j <= val; j++)
运行代码块,然后增加 j
的值,只要j
它就会这样做小于或等于 val
.
因此,对于 j--
j
的序列您拥有的值是 1,0,-1,-2...
而您对 j++
的值序列是1,2,3,4...
运行示例
让我们举个例子,其中val
是 10。与 j++
你的循环将运行 1,2,3,4,5,6,7,8,9,10
然后停止,所以它运行 10 次迭代。与 j--
它将运行 1,0,-1,-2,-3...
.如您所见,这些值离 10 越来越远,这是循环将停止的值。发生的事情是循环一直运行直到你的整数溢出。当您达到 int 的最低可能值时,下一次递减迭代会导致数字的符号翻转并且 j
成为最大可能的整数值,它将大于 10 并打破循环。在 Java 中,int 的标准大小是 32 位,所以最小的整数将是 -(2^31-1)
这是 -2,147,483,648
.因此,如果您使用 j--
运行,您的循环在停止之前将运行超过 20 亿次,这就是运行需要如此多时间的原因。 .
关于java - 超过 Java 阶乘的 Kattis 时间限制,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53676626/