java - 超过 Java 阶乘的 Kattis 时间限制

Question

在试图找到阶乘 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;
 }

我知道第二次迭代没有提供正确的答案，但我很好奇为什么计算第二次而不是第一次循环需要这么长的时间。

Answer 1

循环代码在做什么

For 循环根据 3 个条件多次运行一段代码:

1. 循环变量的起始值(在你的例子中是 int j = 1 )
2. 循环继续的条件(在您的情况下为 j <= val - 因此一旦 j 变得大于或等于 val，它将停止
3. 循环变量随每次迭代而变化的方式(在您的情况下为 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 亿次，这就是运行需要如此多时间的原因。 .