计算阶乘结果的数字尾随零

Question

我正在尝试计算由阶乘产生的数字的尾随零（这意味着数字变得非常大）。 以下代码采用一个数字，计算该数字的阶乘，并计算尾随零。 但是，当数字大约为 25! 时，numZeros 不起作用。

public static void main(String[] args) {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    double fact;
    int answer;
        
    try {
        int number = Integer.parseInt(br.readLine());
        fact = factorial(number);
        answer = numZeros(fact);
    }
    catch (NumberFormatException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    }
}

public static double factorial (int num) {
    double total = 1;
    for (int i = 1; i <= num; i++) {
        total *= i;
    }
    return total;
}   

public static int numZeros (double num) {
    int count = 0;
    int last = 0;   

    while (last == 0) {
        last = (int) (num % 10);
        num = num / 10;
        count++;
    }
    
    return count-1;
}

我并不担心这段代码的效率，而且我知道有多种方法可以使这段代码的效率更好。 我试图弄清楚为什么计算大于 25! 的数字的尾随零不起作用。

有任何想法吗？

Answer 1

您的任务不是计算阶乘，而是计算零的数量。 一个好的解决方案使用 http://en.wikipedia.org/wiki/Trailing_zeros 中的公式（你可以尝试证明这一点）

def zeroes(n):
    i = 1
    result = 0
    while n >= i:
        i *= 5
        result += n/i  # (taking floor, just like Python or Java does)
    return result

希望你能将其翻译成Java。 这只是计算 [n / 5] + [n / 25] + [n / 125] + [n / 625] + ... 并在除数大于 n 时停止。

不要使用大整数。 这是一个 bozosort。 对于大量数据，此类解决方案需要数秒的时间。

Answer 2

您只需要知道产品中有多少个 2 和 5 即可。 如果您计算尾随零，那么您实际上是在计算“10 能除这个数字多少次？”。 如果你代表n！ 为 q*(2^a)*(5^b)，其中 q 不能被 2 或 5 整除。然后，只需在第二个表达式中取 a 和 b 的最小值即可得出 10 能整除该数字的次数。 实际上做乘法是多余的。

编辑：数二也太过分了，所以你只需要五。

对于一些Python，我认为这应该有效：

def countFives(n):
    fives = 0   
    m = 5
    while m <= n:
        fives = fives + (n/m)
        m = m*5
    return fives

Answer 3

double 类型的精度有限，因此如果您使用的数字太大，则 double 将只是一个近似值。 要解决这个问题，您可以使用 BigInteger 之类的东西来使其适用于任意大的整数。

Answer 4

您可以使用 DecimalFormat 来格式化大数字。 如果您以这种方式格式化数字，您会得到科学记数法中的数字，那么每个数字都会就像 1.4567E7 这会让你的工作变得更容易。 因为E后面的数字——后面的字符数。 是我认为的尾随零的数量。

我不知道这是否是所需的确切模式。 您可以在此处查看如何形成模式< /a>

DecimalFormat formater = new DecimalFormat("0.###E0");

Answer 5

我的两点建议：避免使用 double，因为它们容易出错。 在这种情况下，更好的数据类型是 BigInteger，这里有一个小方法可以帮助您：

public class CountTrailingZeroes {

    public int countTrailingZeroes(double number) {
        return countTrailingZeroes(String.format("%.0f", number));
    }

    public int countTrailingZeroes(String number) {
        int c = 0;
        int i = number.length() - 1;

        while (number.charAt(i) == '0') {
            i--;
            c++;
        }

        return c;

    }

    @Test
    public void $128() {
        assertEquals(0, countTrailingZeroes("128"));
    }

    @Test
    public void $120() {
        assertEquals(1, countTrailingZeroes("120"));
    }

    @Test
    public void $1200() {
        assertEquals(2, countTrailingZeroes("1200"));
    }

    @Test
    public void $12000() {
        assertEquals(3, countTrailingZeroes("12000"));
    }

    @Test
    public void $120000() {
        assertEquals(4, countTrailingZeroes("120000"));
    }

    @Test
    public void $102350000() {
        assertEquals(4, countTrailingZeroes("102350000"));
    }

    @Test
    public void $1023500000() {
        assertEquals(5, countTrailingZeroes(1023500000.0));
    }
}

Answer 6

这就是我的制作方法，但是更大的> 25阶乘长容量不够，应该使用Biginteger类，女巫我还不熟悉:)

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner in = new Scanner(System.in);
    System.out.print("Please enter a number : ");
    long number = in.nextLong();
    long numFactorial = 1;

    for(long i = 1; i <= number; i++) {
        numFactorial *= i;
    }
    long result = 0;
    int divider = 5;
    for( divider =5; (numFactorial % divider) == 0; divider*=5) {
         result += 1;
    }

    System.out.println("Factorial of n is: " + numFactorial);
    System.out.println("The number contains " + result + " zeroes at its end.");

    in.close();

 }

}

Answer 7

最好的对数时间复杂度如下：

public int trailingZeroes(int n) {
    if (n < 0)
        return -1;

    int count = 0;
    for (long i = 5; n / i >= 1; i *= 5) {
        count += n / i;
    }

    return count;
}

无耻地从 http 复制://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/

Answer 8

我在 Javascript 中也遇到了同样的问题，我解决了这个问题：

var number = 1000010000;
var str = (number + '').split(''); //convert to string
var i = str.length - 1; // start from the right side of the array
var count = 0; //var where to leave result
for (;i>0 && str[i] === '0';i--){
    count++;
}
console.log(count) // console shows 4

这个解决方案为您提供了尾随零的数量。

var number = 1000010000;
var str = (number + '').split(''); //convert to string
var i = str.length - 1; // start from the right side of the	array
var count = 0; //var where to leave result
for (;i>0 && str[i] === '0';i--){
	count++;
}
console.log(count)

Answer 9

Java 的双倍最大值略高于 9 * 10 ^ 18，而为 25！ 是 1.5 * 10 ^ 25。如果您希望能够拥有那么高的阶乘，您可能需要使用 BigInteger（类似于 BigDecimal 但不执行小数）。

Answer 10

我写得很快，我认为它准确地解决了你的问题。 我使用 BigInteger 类来避免从双精度型到整数型的转换，这可能会给您带来问题。 我对几个超过 25 的大数进行了测试，例如 101，它准确地返回了 24 个零。

该方法背后的想法是，如果你取 25！ 那么第一个计算是 25 * 24 = 600，因此您可以立即去掉两个零，然后执行 6 * 23 = 138。因此，它会计算阶乘以消除零。

public static int count(int number) {
    final BigInteger zero = new BigInteger("0");
    final BigInteger ten = new BigInteger("10");
    int zeroCount = 0;
    BigInteger mult = new BigInteger("1");
    while (number > 0) {
        mult = mult.multiply(new BigInteger(Integer.toString(number)));
        while (mult.mod(ten).compareTo(zero) == 0){
            mult = mult.divide(ten);
            zeroCount += 1;
        }
        number -= 1;
    }
    return zeroCount;
}

既然你说你根本不关心运行时间（并不是说我的第一个特别有效，只是稍微更有效），这个只是执行阶乘然后计算零，所以它在概念上更简单：

public static BigInteger factorial(int number) {
    BigInteger ans = new BigInteger("1");
    while (number > 0) {
        ans = ans.multiply(new BigInteger(Integer.toString(number)));
        number -= 1;
    }
    return ans;
}

public static int countZeros(int number) {
    final BigInteger zero = new BigInteger("0");
    final BigInteger ten = new BigInteger("10");
    BigInteger fact = factorial(number);
    int zeroCount = 0;
    while (fact.mod(ten).compareTo(zero) == 0){
        fact = fact.divide(ten);
        zeroCount += 1;
    }
}