Как найти факториал натурального числа

Иллюстрация: Катя Павловская для Skillbox Media

Даже если вы уже давно окончили школу, факториалы всё равно могут доставить немало приятных флешбэков — например, если вы обучаетесь программированию и знакомитесь с задачками на рекурсию или комбинаторику. Поэтому мы решили максимально просто объяснить, что такое факториал, как его вычислять и зачем он вообще нужен.

Эта статья будет полезна как опытным программистам, которые хотят освежить знания, так и тем, кто ещё учится: школьникам, студентам и совсем зелёным джунам.

Содержание:

• Что такое факториал
• Для чего он нужен
• Основные свойства и формулы
• Шпаргалка: таблица факториалов
• Решаем задачи на факториалы
• Что запомнить

Факториал числа n — это произведение всех натуральных чисел от единицы до n. Обозначается факториал символом восклицательного знака: !.

Это определение из учебника, и оно пока звучит сложновато — неясно, зачем эти факториалы вообще нужны и как они могут пригодиться в науке и технике. Но об этом чуть позже — для начала давайте посмотрим на примеры факториалов:

Чтобы вычислить их, нам нужно перемножить все числа от единицы до числа, стоящего под знаком факториала — так гласит определение. Получаем выражения:

Ещё в математическом определении сказано, что факториал не может быть отрицательным или дробным — то есть вот такие факториалы вычислить нельзя:

Факториалы незаменимы там, где нужно быстро посчитать количество комбинаций и сочетаний разных предметов. В математике этому посвящён даже целый раздел — комбинаторика. Её методы используют много где: от лингвистики до криптографии и анализа ДНК. И во всех этих сферах факториал помогает упрощать сложные вычисления.

Разберём на примере, как это работает.

Допустим, у вас есть пять шоколадок и вы решили раздать их пяти друзьям — каждому по одной. Задача — выяснить, сколько существует способов раздать эти шоколадки. Начинаем размышлять:

• первую шоколадку можно отдать одному из пяти друзей;
• вторую — одному из четырёх друзей, потому что один уже получил свою шоколадку;
• третью — одному из трёх, потому что двое уже наслаждаются своими шоколадками;
• четвёртую — одному из двух;
• пятую — последнему другу.

Получается, что способов раздать первую шоколадку — 5, вторую — 4, третью — 3, четвёртую — 2, а пятую — всего 1. По правилам математики, чтобы выяснить общее количество всех вариантов, нужно перемножить их между собой. Ну а кто мы такие, чтобы с этими правилами спорить?

Смотрим на выражение выше и понимаем: ведь оно идеально вписывается в определение факториала — произведение натуральных чисел от одного до n (в нашем случае n равно 5). Следовательно, это выражение можно коротко и изящно записать в виде факториала:

Выходит, что всего способов раздать пять шоколадок пяти друзьям существует 120. Вот как может выглядеть один из них:

Конечно, в жизни вам вряд ли придётся считать количество способов раздать друзьям шоколадки. Но, например, в статистике, теории вероятностей, матанализе и программировании факториалы используют сплошь и рядом. Так что, если видите себя в будущем на матмехе или, на худой конец, в IT, то лучше познакомиться с ними хотя бы бегло.

Так как факториалы используются в разных областях математики, свойств у них довольно много — каждая область привносит какие-то свои методы вычислений. Одно из свойств вы уже знаете: факториал — это всегда целое положительное число. Вот ещё несколько, которые стоит запомнить:

• Факториал нуля равен единице — 0! = 1.
• Факториал единицы тоже равен единице: 1! = 1.
• Рекурсия: n! = (n – 1)! × n. Это основное свойство факториалов, о нём мы чуть подробнее поговорим дальше.

Мы видим, что каждое свойство описывается какой-то формулой — и некоторые из этих формул могут быть весьма полезны. Они позволяют нам находить факториалы проще и быстрее, чем простым перемножением натуральных чисел. Разберём эти формулы тоже.

Чтобы вычислить факториал, не используя так много операций умножения, придумали формулу Стирлинга. Вот как она выглядит:

Выглядит страшно, но на самом деле она очень полезная. Её используют, когда хотят приблизительно узнать факториал большого числа. Обычным способом это будет сделать сложно даже мощному компьютеру — например, попробуйте посчитать в онлайн-калькуляторе факториал числа 10 024 (спойлер: это может занять несколько часов и даже дней).

Давайте попробуем вычислить факториал числа 6 по этой формуле:

Число e примерно равно 2,71, а π — 3,14. Подставляем их в выражение и получаем ответ:

Получили приближённое значение настоящего факториала, который равен 720. Но можно сделать ответ и более точным. Для этого нужно добавить больше знаков после запятой всем переменным — например, если взять 20 знаков, то ответ будет таким:

Это уже больше похоже на правду. Хотя погрешность всё равно есть.

Рекуррентная формула позволяет вычислить факториал числа n, основываясь на факториале предыдущего числа — (n – 1). Выглядит она так:

В целом рекуррентная формула не приносит нам большой пользы, так как всё равно приходится вычислять факториал предыдущего числа. Если он равен какому-то большому числу (например, 100), то использование формулы теряет смысл — слишком уж много вычислений это потребует.

Однако рекуррентная формула хорошо подходит для алгоритмов — в частности, для программирования. Мы можем задать начальное значение: например, что 0! = 1 или 1! = 1, а затем считать следующие факториалы по формуле:

Получим алгоритм для вычисления факториалов. Не очень эффективный, но простой.

Давайте вычислим по этой формуле факториал числа 4. Сначала распишем рекуррентную формулу до базового значения — факториала числа 1:

Можно записать это и в сокращённом виде:

Теперь последовательно подставляем значение факториала, которое мы уже знаем, и вычисляем результат:

Получили ответ — 24. Ничего сложного, просто перемножаем числа.

Кстати, всю эту формулу можно обернуть в реально работающую функцию на языке Python:

def factorial(n): # Определяем функцию
    if n == 0 or n == 1: # Базовый случай
        return 1
    else: # Рекуррентный случай
        return factorial(n-1) * n # Вызываем эту же функцию, но с меньшим аргументом

print(factorial(4)) # Печатаем факториал 4
# Вывод:
# 24

Можете попробовать запустить её в онлайн-интерпретаторе и посмотреть, как работает. Тут есть один нюанс: Python не даст вам посчитать факториал числа больше 998, так как у него есть ограничение на количество вызовов функции — в программировании это называется глубиной рекурсии.

Чтобы быстро находить, чему равен факториал, можно запомнить или сохранить в заметки вот такую табличку. Она рассчитана всего на 12 чисел, но для большинства учебных задач этого хватит.

С теорией вроде разобрались — теперь попробуем решить несколько задач с факториалами, чтобы закрепить знания на практике.

Задача: перемножить два факториала.

Решение:

Задача: вычесть из одного факториала другой.

Решение:

Задача: умножить один факториал на другой:

Решение:

Задача: сократить дробь и вычислить её значение.

Решение:

Задача: сократить дробь.

Решение:

• Факториал — это произведение всех натуральных чисел от 1 до данного числа. Например, факториал числа 5 будет равен 1 × 2 × 3 × 4 × 5 = 120.
• Его используют во многих областях науки — например, комбинаторике, теории вероятностей и математическом анализе.
• Помимо стандартной формулы для вычисления факториала можно использовать формулы Стирлинга и рекуррентную формулу.
• Формула Стирлинга нужна для того, чтобы посчитать факториал без большого числа операций умножения.
• Рекуррентная формула позволяет вычислить факториал на основе предыдущего факториала.