找到Factorial Trailing Zero时的结果不一致

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

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

这是由于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 

正如你在这里看到的1220703125 ，当n = 1时， base增加到1220703125然后语句base *= 5运行使得6103515625超过最大32位unsigned int（ 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 。