JavaScript

Помощь с алгоритмом.

Помогите составить алгоритм для которой передаётся два параметра. Число и система счисления. Суть в том, чтобы найти количество нулей на конце факториала независимо от системы счисления. Сам факториал считать нерационально. Для нахождения количества нулей в десятичной системе нужно пройти по циклу, где число делется на 5, потом на 5^2, потом на 5^3 и т. д. А вот оптимизировать для любой системы счисления я не могу придумать.
RR
Rap Rap Rap
119
Техника такая
Основание системы раскладываем на простые делители ( для десятичной это 2*5, для каждого делителя не забываем указать необходимое количество => 1 двойка+1 пятерка, для 16-ричной 4 двойки)
далее берем текущий множитель, раскладываем на простые делители и считаем количество делителей для каждого из делителей основания системы - например 12 = 2*2*3 ( +2 делителя №1 )
После окончания цикла по множителям считаем минимальное количество делителей (с учетом требуемого) - получаем количество нулей в конце

https://ideone.com/BjJzIg
K_
Kandi _*
51 507
Лучший ответ
Rap Rap Rap немного не понимаю.
шаг 1) разлаживаю систему счисления на простые числа и запоминаю количество этих простых чисел. ( например для сс 45 - это разложение будет 2^3 * 5)
шаг 2) куда смотреть?) понятно, что нуно выбрать большее из простых чисел, но учитывать ли степень? сравнивать 2 и 5 или 9 и 5? И что в дальнейшем делать со степенями.
p.s. ваш код просмотрел, но мало чего понял (далёк от с++), но всё-равно спасибо)
Rap Rap Rap я разобрался)
Rap Rap Rap если кому-нибудь нужен будет код на js, он на моёт гитхабе spacebrains/advanced-zeros
ff=(a,b)=>(console.log(b,a.toString(b).replace(/[1-9a-z]/g,'').length),b<36&&ff(a,b+1))

ff(152556204,2)
a Это число b это начальная система исчисления
в итоге в консоли получаем список в первая цифра это система исчисления вторая цифра количество обнаруженных нулей системы исчисления от 2 до 36

⚤
Sergey Parakschin
Sergey Parakschin
64 531
Алгоритма для десятичной так и не понял. Поподробнее что и зачем надо делить? То что факториал считать не рационально, это понятно. Непонятно что и на что надо делить. А суть такова что если умножить число на основание системы то это ноль в конце! Любое число умножить на 10 в десятичной и получим 0 в конце, например 2*10 = 20. Как и любое число в двоичной умножить на два, например 11(3 в десятичной) * 10(2 в десятичной) = 110(6 в десятичной). Второе правило - количество нулей зависит от степени основания. 10 ^ 2 - два нуля для десятичной. 2 ^ 2 - два нуля для двоичной. 16^2 - два нуля для шестнадцатиричной
Артём Петрусенко
Артём Петрусенко
15 398
Kandi _* Нужно не забывать, что кроме чисел с "основанием" есть еще и входящие в него множители
например для 10 это 2 и 5
получаем, что в 10! кроме последней 10, у нас еще есть (как минимум) еще множители 2 и 5, которые "добавят" еще один нолик

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