计算数字的尾随零是由因子计算的 [英] Counting trailing zeros of numbers resulted from factorial

问题描述

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

I'm trying to count trailing zeros of numbers that are resulted from factorials (meaning that the numbers get quite large). Following code takes a number, compute the factorial of the number, and count the trailing zeros. However, when the number is about as large as 25!, numZeros don't work.

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！不工作。

I am not worrying about the efficiency of this code, and I know that there are multiple ways to make the efficiency of this code BETTER. What I'm trying to figure out is why the counting trailing zeros of numbers that are greater than 25! is not working.

任何想法？

推荐答案

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

Your task is not to compute the factorial but the number of zeroes. A good solution uses the formula from http://en.wikipedia.org/wiki/Trailing_zeros (which you can try to prove)

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时停止。

Hope you can translate this to Java. This simply computes [n / 5] + [n / 25] + [n / 125] + [n / 625] + ... and stops when the divisor gets larger than n.

请勿使用BigIntegers。这是一个bozosort。对于大数字，这样的解决方案需要几秒钟的时间。

DON'T use BigIntegers. This is a bozosort. Such solutions require seconds of time for large numbers.

这篇关于计算数字的尾随零是由因子计算的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！