java - 查找阶乘尾随零时的结果不一致

Question

这是我编写的两个版本的代码，用于返回 n! 中尾随零的数量。第一个版本为输入 1808548329 返回 452137080，第二个版本为输入 1808548329 返回 452137076。想知道为什么会有差异？第二个版本的输出是正确的。

Java源代码,

public class TrailingZero {
    public static int trailingZeroes(int n) {
        int result = 0;
        int base = 5;
        while (n/base > 0) {
            result += n/base;
            base *= 5;
        }

        return result;
    }

    public static int trailingZeroesV2(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroesV2(n / 5);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(trailingZeroes(1808548329));
        System.out.println(trailingZeroesV2(1808548329));
    }
}

Answer 1

这是由于 integer overflow在 base 的值中。

稍微更改您的代码以打印 n/base 和 base:

public class TrailingZero {
    public static int trailingZeroes(int n) {
        int result = 0;
        int base = 5;
        while (n/base > 0) {
            System.out.println("n = " + n/base  + " base = " + base);
            result += n/base;
            base *= 5;
        }

        return result;
    }

    public static int trailingZeroesV2(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroesV2(n / 5);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(trailingZeroes(1808548329));
        System.out.println(trailingZeroesV2(1808548329));
    }
}

输出:

n = 361709665 base = 5
n = 72341933 base = 25
n = 14468386 base = 125
n = 2893677 base = 625
n = 578735 base = 3125
n = 115747 base = 15625
n = 23149 base = 78125
n = 4629 base = 390625
n = 925 base = 1953125
n = 185 base = 9765625
n = 37 base = 48828125
n = 7 base = 244140625
n = 1 base = 1220703125
n = 1 base = 1808548329   <== OOPS 6103515625 overflows 32-bit integer
n = 3 base = 452807053
452137080

正如您在此处看到的，当 n =1 时，base 增加到 1220703125。然后语句 base *= 5 运行，这使得 6103515625 超过最大 32 位无符号整数 (2^32) 6103515625 - 2^32 = 1808548329，这就是您在上面看到的 b 的中间错误值(OOPS)。

另一方面，递归解决方案仅使用不断减小的n 的值。因此没有溢出。

简单的解决方案是将 base 声明为 long，即 long base = 5。这将返回 452137076 的正确值。

另一种解决方案是将循环修改为仅使用 n，类似于递归解决方案:

    int base = 5;
    while (n > 0) {
        result += n/base;
        n = n/base;
    }

请注意，在涉及阶乘的问题中，溢出是给定的，您可能需要考虑更高精度的算术，例如 BigInteger .