Другие языки программирования и технологии

На сколько нулей оканчивается факториал заданного числа

Напишите программу (а она очень простая) , которая находит, на сколько нулей оканчивается факториал заданного числа.
Надо, чтобы считало для всех чисел, влезающих в диапазон 32-битного целого.
Проверю ваши знания, затем приведу свой алгоритм.
Хм, до логарифма, признаюсь, не додумал.
Пока код отлаживал, ответ выложили.

У меня вот так: http://pastebin.com/WtP6RNjT
Диман И Ксюша Кашины
Диман И Ксюша Кашины
13 097
Лучший ответ
Виктор Колотов Все правильно. Кроме того, ваш алгоритм целочисленный и не использует плавающую точку. Пожалуй, так даже еще лучше.
(2^32)! займет чуть более 15 ГБ памяти. При современных вычислительных мощностях это число можно посчитать абсолютно точно за вполне конечное время. Ну да мы пойдем другим путем.
Я бы просто перемножал соседние числа и смотрел, сколько в результате получается нулей. Только надо после каждой "удачной попытки" прыгнуть на 1 вперед, чтобы 2 раза тот же 0 не считать. Проверим для 25:

1*2=2 0
2*3=6 0
3*4=12 0
4*5=20 1
6*7=42 1
7*8=56 1
8*9=17 1
9*10=90 2
11*12=132 2
12*13=156 2
13*14=182 2
14*15=210 3
16*17=272 3
17*18=306 3
18*19=342 3
19*20=380 4
21*22=462 4
22*23=506 4
23*24=552 4
24*25=600 6

25!=15511210043330985984000000 - вроде верно.
Ержан Шабдезим
Ержан Шабдезим
87 140
Виктор Колотов Оригинальный алгоритм, хотя я суть немного не догнал. А на 100 даст 24?
Он будет работать O(X), мой алгоритм за O(log X).
причем тут математика и программирование? лично для меня - вычисление факториала и все сопутствующее с ним - пустая трата моего времени
Дмитрий Белкин
Дмитрий Белкин
92 932
Виктор Колотов Вы сейчас время на ответ потратили. Не понимаю, зачем
Я не великий программист, и вычислять факториал больших чисел мне не надо, поэтому обхожусь для вычисления простой рекурсией.

P.S. Интересно было бы взглянуть на алгоритм. Думаю что это разложение на пары числе 2 и 5 или как там оно правильно...
Виктор Колотов Подскажу. Сам факториал вычислять не надо, такой задачи не ставилось.
Если что, 13! уже не влезает в 32-битное число (6,2 млрд) . А меня интересует факториал 32-битного числа, например 100000!
Виктор Колотов Пятерок хватит, двоек все равно будет больше.
Надо определить, сколько раз число делится на 5. Если оно меньше 25, достаточно поделить на 5 с округлением вниз до целого.
Если же оно = 25, то 25 делится на 5 дважды.
В общем, алгоритм такой: найти, сколько чисел в интервале 1...N делится на 5, плюс сколько чисел делится на 25, плюс сколько чисел делится на 125 и т. д. понятно, что есть смысл выполнять только до log_5 N, дальше будут нули.
на беглый взгляд (осторожнее - могу наврать, особенно с индексами) :

int colvo=0;
for( int i=1,col=0;i<n/5;i++){
colvo++;//учёт пятерок
int tmp=i;
while(tmp%5?0:tmp/=5)colvo++;//учет составных пятерок
}

а к каждой пятёрке меньшая двойка найдётся и вместе дадут очередной ноль в конце числа (он только от 5*2)
Сергей Никонов
Сергей Никонов
27 060
Не очень понял суть проблемы. Тем более сравнивать алгоритмы, не указывая заранее критерий сравнения.

Задача эквивалентна следующей:
Найти суммарное количество делителей, равных 5, среди всех чисел 1..X для любого X из диапазона [1, 2^32].

Просто в лоб:
Cnt(X, 5) + Cnt(X, 25) + Cnt (X, 625) + и так далее до 5^13 (последнее <= 2^32)
Где Cnt(X, A) - количество чисел, не превосходящих X, делящихся на A.
Cnt(X, A) = X div A // целочисленное деление X на A.

ЗЫ. Писать это дольше, чем придумывать.
Вадим Кузнецов
Вадим Кузнецов
11 112
function fact_z(int) { return Math.floor(int / 5); }
Вот так легко это находится ))
Заметил закономерность. .

Комменты у меня запрещены
При инт равном 25 возвращает 5, а при 100 очевидно 20..

Женя Павлов
Женя Павлов
2 501
Виктор Колотов Скажем, для int = 15
Виктор Колотов Скомпилируйте, проверьте...
Виктор Колотов Я уже молчу про int = 10000 например.
Виктор Колотов Нет, не 15. Возьмем 25. Или лучше 100.
Виктор Колотов Открываем в 7-й винде калькулятор, вводим 25!, получаем ШЕСТЬ нулей на конце. А по поводу 100! тут был ответ Михаила Левина на какой-то вопрос, найти его будет трудно, но там 24 нуля (он привел факториал полностью, там видно)
Виктор Колотов В принципе в правильном направлении идете, надо только доработать идею. Подумайте, почему для 24 ваш алгоритм даст правильный результат, а для 25 уже нет. А на 50 будет ошибаться на 2.
Виктор Колотов Выложил алгоритм.

Похожие вопросы