Напишите программу (а она очень простая) , которая находит, на сколько нулей оканчивается факториал заданного числа.
Надо, чтобы считало для всех чисел, влезающих в диапазон 32-битного целого.
Проверю ваши знания, затем приведу свой алгоритм.
Другие языки программирования и технологии
На сколько нулей оканчивается факториал заданного числа
Хм, до логарифма, признаюсь, не додумал.
Пока код отлаживал, ответ выложили.
У меня вот так: http://pastebin.com/WtP6RNjT
Пока код отлаживал, ответ выложили.
У меня вот так: http://pastebin.com/WtP6RNjT
Виктор Колотов
Все правильно. Кроме того, ваш алгоритм целочисленный и не использует плавающую точку. Пожалуй, так даже еще лучше.
(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 - вроде верно.
Я бы просто перемножал соседние числа и смотрел, сколько в результате получается нулей. Только надо после каждой "удачной попытки" прыгнуть на 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 - вроде верно.
Виктор Колотов
Оригинальный алгоритм, хотя я суть немного не догнал. А на 100 даст 24?
Он будет работать O(X), мой алгоритм за O(log X).
Он будет работать O(X), мой алгоритм за O(log X).
причем тут математика и программирование? лично для меня - вычисление факториала и все сопутствующее с ним - пустая трата моего времени
Виктор Колотов
Вы сейчас время на ответ потратили. Не понимаю, зачем
Я не великий программист, и вычислять факториал больших чисел мне не надо, поэтому обхожусь для вычисления простой рекурсией.
P.S. Интересно было бы взглянуть на алгоритм. Думаю что это разложение на пары числе 2 и 5 или как там оно правильно...
P.S. Интересно было бы взглянуть на алгоритм. Думаю что это разложение на пары числе 2 и 5 или как там оно правильно...
Виктор Колотов
Подскажу. Сам факториал вычислять не надо, такой задачи не ставилось.
Если что, 13! уже не влезает в 32-битное число (6,2 млрд) . А меня интересует факториал 32-битного числа, например 100000!
Если что, 13! уже не влезает в 32-битное число (6,2 млрд) . А меня интересует факториал 32-битного числа, например 100000!
Виктор Колотов
Пятерок хватит, двоек все равно будет больше.
Надо определить, сколько раз число делится на 5. Если оно меньше 25, достаточно поделить на 5 с округлением вниз до целого.
Если же оно = 25, то 25 делится на 5 дважды.
В общем, алгоритм такой: найти, сколько чисел в интервале 1...N делится на 5, плюс сколько чисел делится на 25, плюс сколько чисел делится на 125 и т. д. понятно, что есть смысл выполнять только до log_5 N, дальше будут нули.
Надо определить, сколько раз число делится на 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)
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)
Не очень понял суть проблемы. Тем более сравнивать алгоритмы, не указывая заранее критерий сравнения.
Задача эквивалентна следующей:
Найти суммарное количество делителей, равных 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.
ЗЫ. Писать это дольше, чем придумывать.
Задача эквивалентна следующей:
Найти суммарное количество делителей, равных 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.
ЗЫ. Писать это дольше, чем придумывать.
function fact_z(int) { return Math.floor(int / 5); }
Вот так легко это находится ))
Заметил закономерность. .
Комменты у меня запрещены
При инт равном 25 возвращает 5, а при 100 очевидно 20..

Вот так легко это находится ))
Заметил закономерность. .
Комменты у меня запрещены
При инт равном 25 возвращает 5, а при 100 очевидно 20..

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