发现阶乘尾随零时结果不一致 [英] inconsistent results when finding Factorial Trailing Zero

问题描述

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

Here are two versions of code I write to return the number of trailing zeroes in n!. The first version returns 452137080 for input 1808548329, the 2nd version returns 452137076 for input 1808548329. Wondering why there is a difference? The output from 2nd version is correct.

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));
    }
}

推荐答案

此是由于整数溢出的值 base 。

稍微更改代码以打印 n / base 和 base ：

Changing your code slightly to print n / base and 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时，c $ c> base 增加到 1220703125 。然后语句 base * = 5 运行，这使得它 6103515625 超出了最大32位无符号整数（ 2 ^ 32 ）恰好是 6103515625-2 ^ 32 = 1808548329 ，这就是中间错误值 b 以上（ OOPS ）。

As you can see here, base increases to 1220703125, when n =1. Then the statement base *= 5 runs which makes it 6103515625 which is overshoots the maximum 32-bit unsigned int (2^32) by exactly 6103515625 - 2^32 = 1808548329, and that is what you see as the intermediate wrong value of b above (OOPS).

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

On the other hand, the recursive solution only uses the value of n which continuously decreases. Hence there is no overflow.

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

The simple solution is to declare base as long, i.e., long base = 5. That will return the right value of 452137076.

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

Another solution will be to modify the loop to only use n, similar to the recursive solution:

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

请注意，在涉及阶乘的问题中，溢出是给定的，您可能想要考虑使用诸如 BigInteger 之类的高精度算术。

Note that in problems involving factorials, overflow is a given and you may want to consider higher precision arithmetic such as BigInteger.

这篇关于发现阶乘尾随零时结果不一致的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！