计算数字的尾随零是由因子计算的

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

不要使用BigIntegers.这是一个bozosort.这种解决方案需要几秒钟才能获得大量数据.

Answer 2

您只需要知道产品中有多少2和5.如果你正在计算尾随零,那么你实际上是在计算"十次除以这个数字的次数是多少？".如果你代表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