Что такое факториал и как его вычислить
2026-02-21 03:23 Diff
https://skillbox.ru/media/code/chto-takoe-faktorial-i-kak-ego-vychislit/

#статьи

  • 19 май 2023
  • 0

Что такое факториал и как его вычислить

Статья, после которой вы начнёте щёлкать факториалы как орешки.

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

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

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

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

Содержание:

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

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

Изображение: Skillbox Media

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

Изображение: Skillbox Media

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

Изображение: Skillbox Media

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

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

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

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

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

Изображение: Skillbox Media

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

Изображение: Skillbox Media

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

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

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

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

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

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

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

Изображение: Skillbox Media

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

Онлайн-калькулятор не справился с вычислением такого большого числа, как факториал 10 024
Скришнот: «Контрольная работа РУ — калькуляторы онлайн» / Skillbox Media

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

Изображение: Skillbox Media

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

Изображение: Skillbox Media

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

Изображение: Skillbox Media

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

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

Изображение: Skillbox Media

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

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

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

Изображение: Skillbox Media

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

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

Изображение: Skillbox Media

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

Изображение: Skillbox Media

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

Изображение: Skillbox Media

Получили ответ — 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!12!23!64!245!1206!7207!50408!40 3209!362 88010!3 628 80011!39 916 80012!479 001 600

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

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

Изображение: Skillbox Media

Решение:

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

Изображение: Skillbox Media

Обратите внимание: во второй строке мы применили рекуррентную формулу, чтобы быстрее вычислить факториал числа 7.

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

Изображение: Skillbox Media

Решение:

Используем тот же подход, что и в предыдущей задаче: сначала вычисляем факториалы, а затем получаем ответ на всё выражение.

Изображение: Skillbox Media

Вроде бы ничего сложного, главное — не запутаться в умножении.

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

Изображение: Skillbox Media

Решение:

Вычисляем факториалы, потом перемножаем их значения:

Изображение: Skillbox Media

Во второй строке мы воспользовались таблицей выше и быстро нашли значение факториала от числа 8.

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

Изображение: Skillbox Media

Решение:

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

Изображение: Skillbox Media

В первой строке мы применили рекуррентную формулу два раза, а во второй — просто сократили одинаковые факториалы в числителе и в знаменателе.

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

Изображение: Skillbox Media

Решение:

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

Изображение: Skillbox Media

Главное — не запутаться и правильно применить рекуррентную формулу.

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