Подсчет конечных нулей факториала числа в любой системе счисления
Как я могу посчитать количество конечных нулей факториала числа в определенной системе счисления?
Давайте рассмотрим случай, когда мы находимся в 10-й системе счисления, а затем посмотрим, как мы можем обобщить это в универсальное решение. Нам дано число N и для его факториала нужно найти количество конечных нулей. Решение будет довольно простым — сумма:
Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + . Её мы можем обобщить в такую формулу:
Почему 5? Это просто. Конечный ноль получается только тогда, когда в составе факториала число имеет 10. Таким образом, посчитав количество десяток в факториале, мы узнаем количество конечных нулей.
Почему в примере выше мы делим на 5? Потому что 10 может быть получено умножением 5 на 2. Поэтому полное решение будет иметь две формулы:
Но, рассуждая логически, мы знаем, что первая сумма будет меньше, поэтому нам нужно посчитать только её (подробнее можно почитать тут).
Решение нашей проблемы
Для подсчёта конечных нулей факториала числа в определенной системе счисления я составил алгоритм, приведенный ниже:
- Разложить число B системы счисления на простые множители.
- Разделить число N на каждый уникальной простой множитель K, домножая K сам на себя до тех пор, пока будет больше единицы, при этом округляя каждый результат до меньшего целого.
- Если при разложении числа системы счисления мы получили несколько одинаковых простых множителей K, то результат выше мы должны разделить на количество одинаковых K.
- Из всех делений N на каждый уникальный множитель K выбрать наименьшее частное, которое и будет нашим ответом.
Но двойка встречалась дважды при разложении 12-и, поэтому конечный результат мы делим на 2 и округляем до меньшего целого. В результате получаем 1.
Проделываем тоже самое с 3:
Таким образом, мы получили два частных от делений числа N на простые множители числа системы счисления. Они оба равны 1, поэтому меньшее нам выбирать не приходится и мы просто даем ответ — 1.
Рассмотрим еще один пример.
Пусть число N = 16, система счисления B = 16. Факториал 16! = 20922789888000, а 20922789888000 в 16-ой системе — 130777758000. Мы видим, что в конечной системе счисления факториал исходного числа имеет три ноля. При разложении 16 на простые множители, получим 2, 2, 2, 2. Здесь у нас только одно уникальное число, поэтому пункт 2 выполняется только один раз:
При разложении у нас было четыре двойки, поэтому сумму делений делим на 4 с округлением до меньшего целого:
P.S. Большую часть материала для поста перевел отсюда. Автор — Aditya Ramesh.
- mathematics
- algorithms
50! — Факториал из 50
Факториал 50 содержит 65 цифр. Количество нулей в конце — 12.
3041409320 1713378043 6126081660 6476884437 7641568960 5120000000 00000
Факториал из пятьдесят
инструкции
Введите целое число 0- 50 000. Калькулятор вычислит факториал и количество содержащихся в нем цифр.
Что такое факториал?
Факториал N — это произведение всех положительных целых чисел от 1 до N включительно. Например, факториал 5 равен 5×4×3×2×1=120. Единственным исключением является 0 !, который определяется как 1. Факториалы отрицательных чисел не определены.
Факториалы распространены в различных разделах математики, включая комбинаторику , теорию чисел и разложения Тейлора .
Количество конечных нулей
Чтобы определить количество нулей в конце факториала, рекурсивно разделите число на 5, пока частное не станет меньше 5, и просуммируйте результаты после применения функции наибольшего целого числа.
Наибольшая целочисленная функция (обычно обозначается скобками) — это округленное в меньшую сторону целое число. Например, [5] = 5, [4.5] = 4, [-4.5] = -5.
Например, количество нулей в конце в 50! равно ([50/5]=10) + ([10/5]=2) = 12.
Digits in 50!
| Digit | Count |
|---|---|
| 0 | 19 (29.23%) |
| 1 | 7 (10.77%) |
| 2 | 3 (4.62%) |
| 3 | 6 (9.23%) |
| 4 | 7 (10.77%) |
| 5 | 2 (3.08%) |
| 6 | 9 (13.85%) |
| 7 | 5 (7.69%) |
| 8 | 5 (7.69%) |
| 9 | 2 (3.08%) |
| Total | 65 |
| Digit Sum | 216 |
Примеры
More about 50
- Facts about 50
- Gamma of 50
- 50 Fibonacci Number
- 50 Bernoulli Number
- 50 Euler Number
Сколько нулей в конце у факториала
Условие : Write a program that will calculate the number of trailing zeros in a factorial of a given number. N! = 1 * 2 * 3 * . * N Be careful 1000! has 2568 digits. For more info, see: http://mathworld.wolfram.com/Factorial.html Examples
zeros(6) = 1 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720 --> 1 trailing zero zeros(12) = 2 12! = 479001600 --> 2 trailing zeros Hint: You’re not meant to calculate the factorial. Find another way to find the number of zeros. Как мы видим в последней строчке, вычислять факториал не требуется. Но для понимания картины я решил это сделать.
public static int zeros(int n) < BigInteger x = BigInteger.ONE; BigInteger temp = BigInteger.ONE; while (!x.toString().equals(String.valueOf(n))) < temp = temp.multiply(x); x = x.add(BigInteger.ONE); >System.out.println(temp); String tempStr = String.valueOf(temp); int countZero = 0; for(int i = 0 ; i < tempStr.length() ; i ++)< countZero = tempStr.charAt(i)=='0' ? countZero+1 : 0; >return countZero; >
Пробуем N = 1000; Результат : 246. На мой взгляд решение верное (по условию), но ответ неверный. Должно быть 249. Стал копать. Наткнулся на это https://www.geeksforgeeks.org/count-trailing-zeroes-factorial-number/ Ну и ниже решение :
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; > Пожалуйста, помогите разобраться почему мой код не верен, и что написано в пояснении к решению задачи?
Анализ алгоритма
Факториал числа n равен произведению чисел от 1 до n. Ноль в конце произведения появляется в результате перемножения 2 и 5. Но поскольку при разложении на простые множители числа n! двоек больше чем пятерок, то количество нулей в конце n! равно количеству пятерок в разложении n! на простые множители. Это число равно
Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.
Найдем количество нулей, которыми заканчивается 100!
Третье слагаемое уже равно нулю, так как 100 < 5 3 = 125.
Читаем значение n.
Вычисляем по формуле ответ .