Факториал задачи: базовые понятия
На экзамене школьники часто встречаются с формулировкой «вычислите n!». Факториал задачи выглядит просто: нужно перемножить все целые числа от единицы до n. Однако даже такой, казалось бы, прямолинейный шаг вызывает вопросы. Сначала определимся: 0! равен единице по соглашению, потому что так корректно продолжается рекуррентная формула n!=n·(n-1)!. Далее важно помнить о быстром росте результата: уже 20! почти девятнадцать цифр. Поэтому при решении заданий ЕГЭ мы редко считаем полный факториал вручную. Чаще нужно проанализировать последнюю цифру, количество нулей или сравнить два произведения. Разобрав общий принцип, станет проще узнавать подобные номера в вариантах.
Минимальный набор свойств
Первое свойство: если n больше m, то n! кратен m!. Это сразу сокращает многие дроби. Второе: в разложении n! на простые множители показатель степени простого числа p равен сумме ⌊n/p⌋+⌊n/p²⌋+… . Формула Лежандра часто встречается в сложных задачах. Третье свойство пригодится при делении: n!/(n-k)! равно произведению k последовательных чисел. Четвёртое: факториал быстро превышает 32-битные границы, поэтому в программах используем типы long long или BigInteger. Запомнив эти пункты, вы уже снимаете половину ловушек, подготовленных составителями.
Прямое вычисление и его ограничения
Иногда задание просит вывести точное значение n!, где n не превышает 10. Здесь достаточно цикла и переменной-накопителя. Код на Python:
- ans=1
- for i in range(2, n+1): ans*=i
В других языках алгоритм идентичен. Проблема начинается при n≥30: стандартный тип int переполняется. Тогда в C++ подключаем библиотеку Boost.Multiprecision, а в Java – класс BigInteger. На экзамене по информатике обычно не дают таких больших n, но знать границы всё равно полезно. Если требуется только вывести «YES» или «NO», считать весь факториал не нужно, достаточно проверок делимости или сравнения степеней.
Оптимизация: хранение и делимость
При работе с огромными числами важен каждый байт. Нужно ли хранить все множители? Чаще нет. Например, чтобы выяснить, делится ли n! на 2⁵·5³, достаточно убедиться, что n≥15. Такая экономия решает две задачи: ускоряет программу и убирает риск переполнения. Полезный приём – считать только необходимое число факторов двойки и пятёрки для поиска хвостовых нулей. Преподаватели советуют выписывать множители на черновике, отмечая нужные степени. Метод дисциплинирует мышление и избегает ошибок округления.
Классическая задача про количество нулей
Составители любят спрашивать: «Сколько нулей оканчивает n!?». Ответ зависит от минимальной степени чисел 2 и 5. Двоек всегда больше, поэтому считаем пятёрки: k=⌊n/5⌋+⌊n/25⌋+… . Например, 100! имеет 24 нуля, потому что 100/5=20 и 100/25=4. Запомните: деление округляется вниз. Проверим себя: 4*25=100, значит учли максимальную степень. На ЕГЭ формула приносит лёгкие баллы, потому что расчет занимает меньше минуты.
Комбинаторные применения
Формулы размещений A(n,k)=n!/(n-k)! и сочетаний C(n,k)=n!/k!/(n-k)! сразу показывают, почему факториал задачи встречаются так часто. Знание свойств факториала помогает упростить выражения, сокращая одинаковые части дроби. Например, при n=12 и k=10 лучше преобразовать A(12,10) в 12·11. Мы сокращаем десять факторов и избегаем гигантского промежуточного результата. Такой подход снижает вероятность вычислительных промахов и экономит время.
Рекурсия и динамика в коде
Материалы ЕГЭ допускают написание рекурсивной функции factorial(n). Но прямой вызов стеково неэффективен: глубина растёт вместе с n. Лучше объединить идею рекурсии с мемоизацией. Храним уже найденные значения в массиве или словаре, затем возвращаем готовый ответ. Для n≤20 получаем мгновенный результат, а программа остаётся компактной. На экзамене жизненно важно обернуть рекурсию проверкой: if n in memo. Тогда даже слабый компьютер в аудитории успеет выполнить код за отведённое время.
Частые ошибки и полезные сервисы
Первая ошибка – лишние умножения при упрощении дробей. Вторая – невнимательность при подсчёте степеней пятёрки. Третья – использование типа int там, где нужен long long. Четвёртая – отсутствие округления вниз при делении. Чтобы избежать подобных промахов, решайте тесты каждую неделю, проверяя ответы на открытых тестовых платформах. Если хочется структурного курса, загляните в онлайн школу подготовки к ЕГЭ по информатике. Там собраны задачи разного уровня, а преподаватель разберёт каждое решение, что особенно ценно во время самостоятельной тренировки.