Сколько ноль итого в 100 факториале

Question

У меня есть домашняя работа, которая считает ноль в n факториалах. Что я должен делать? Я только нахожу способ посчитать трейлинг факториала

static int findTrailingZeros(int n) 
{ 
    // Initialize result 
    int count = 0; 

    // Keep dividing n by powers  
    // of 5 and update count 
    for (int i = 5; n / i >= 1; i *= 5) 
        count += n / i; 

    return count; 
} 

Answer 1

Общее количество нулей в n! определяется последовательностью A027869 в Онлайн-энциклопедии целочисленных последовательностей.Кажется, на самом деле нет никакого способа вычислить общее число нулей в n!, за исключением вычисления n! и подсчета количества нулей.С большой библиотекой int это достаточно просто.Простой пример Python:

import math

def zeros(n): return str(math.factorial(n)).count('0')

Так, например, zeros(100) оценивается как 30.Для больших n вы можете пропустить относительно дорогое преобразование в строку и получить арифметический счет 0, многократно разделив на 10.

Как вы заметили, вычислить намного прощечисло конечных нулей.Ваш код на Python, по сути, выглядит следующим образом:

def trailing_zeros(n):
    count = 0
    p = 5
    while p <= n:
        count += n//p
        p *= 5
    return count

В качестве эвристического способа оценки общего числа нулей вы можете сначала посчитать количество конечных нулей, вычесть это число из числа цифр в * 1018.*, вычтите еще 2 из этой разницы (поскольку ни первая цифра n!, ни последняя цифра перед конечными нулями не являются позициями-кандидатами для непоследовательных нулей) и предположите, что 1/10 из этих цифр фактически будет нулями,Вы можете использовать формулу Стирлинга для оценки количества цифр в n!:

def num_digits(n):
    #uses Striling's formula to estimate the number of digits in n!
    #this formula, known as, Kamenetsky's formula, gives the exact count below 5*10^7
    if n == 0:
        return 1
    else:
        return math.ceil(math.log10(2*math.pi*n)/2 + n *(math.log10(n/math.e)))

Следовательно:

def est_zeros(n):
    #first compute the number of candidate postions for non-trailing zerpos:
    internal_digits = max(0,num_digits(n) - trailing_zeros(n) - 2)
    return trailing_zeros(n) + internal_digits//10 

Например, est_zeros(100) равно 37, что не очень хорошо, но тогда нет оснований полагать, что эта оценка лучше асимптотической (хотя доказательство , что она асимптотически правильная, было бы очень сложно, я на самом деле не знаю,это).Для больших чисел это, кажется, дает разумные результаты.Например zeros(10000) == 5803 и est_zeros == 5814.

Answer 2

100! большое число:

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Чтобы быть более точным, требуется ~ 525 бит и не может быть вычислено без какой-либо формы bigint математики.

Однако конечные нули могут быть вычислены на обычных целых числах:

Идея состоит в том, чтобы ограничить результат по-прежнему вписываться в ваш тип данных. Поэтому после каждого итерационного теста результат делится на 10. Если он увеличивается, то счетчик нулей увеличивается и делится на 10, пока вы можете. То же самое относится и к любым простым числам, кроме тех, которые делят 10, поэтому нет: 2,5 (но без увеличения счетчика нулей). Таким образом, у вас будет небольшой промежуточный результат и количество конечных нулей.

Таким образом, если вы выполните 2,5 факторизацию всех мультипликаторов в n!, то минимальное значение обоих показателей в 2,5 будет равно числу конечных нулей, поскольку каждая пара выдает одну нулевую цифру (2*5 = 10). Если вы понимаете, что показатель 5 всегда меньше или равен показателю 2, этого достаточно для факторизации 5 (так же, как вы делаете это в своем обновленном коде).

int fact_trailing_zeros(int n)
    {
    int i,n5;
    for (n5=0,i=5;n>=i;i*=5) n5+=n/i;
    return n5;
    }

С результатами:

Trailing zeors of n!
       10! :         2
      100! :        24
     1000! :       249
    10000! :      2499
   100000! :     24999
  1000000! :    249998
 10000000! :   2499999
100000000! :  24999999
[   0.937 ms]

Однако 100! содержит также непоследних нулей и для вычисления тех, которые я не вижу другого способа, кроме вычисления реальной вещи по bigint математике ... но это не означает, что нет обходного пути как для конечных нулей ...

Если это поможет, здесь вычисляются факториалы вплоть до 128!, поэтому вы можете проверить свои результаты:

• Быстрый точный факториал bigint

Если n ограничено достаточно малым значением, вы можете использовать LUT , сохраняя все факториалы до предела в виде строк, или BCD и просто отсчитывать нули оттуда. .. или даже иметь только окончательные результаты в виде LUT ...

Answer 3

Как насчет этого.

count = 0
s = str(fact)
for i in s:
    if i=="0":
        count +=1
print(count)