Factorial
Факториал целого числа n, обозначаемый n!, — это произведение всех целых чисел от 1 до n. Например, 4! = 1 × 2 × 3 × 4 = 24. По определению 0! = 1. Ваша функция получает n и возвращает n!.
Функция
- ninteger
- целое число, факториал которого вы вычисляете
- Возвращаетinteger
- произведение всех целых чисел от 1 до n, которое равно 1, если n равно 0
Ограничения
0 ≤ n ≤ 12- Ответ помещается в знаковое 32-битное целое число: наибольшее из них —
12! = 479001600.
Примеры
- Ввод
- n = 5
- Вывод
- 120
- Пояснение
- Перемножьте
1 × 2 × 3 × 4 × 5. Промежуточное произведение равно 1, 2, 6, 24 и в итоге составляет 120.
- Ввод
- n = 0
- Вывод
- 1
- Пояснение
- Здесь нечего умножать, а произведение без множителей равно
1. Вот почему0! = 1.
+11 скрытых тестов при отправке
Дополнительный вопрос
100! состоит из 158 цифр. Можешь посчитать, сколько нулей стоит в конце, не вычисляя его?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Запишите
4!и5!в виде произведений. Как5!связано с4!?5! = 5 × 4!. В общем случаеn! = n × (n-1)!, и цепочка завершается на0! = 1.Поддерживай текущее произведение, начиная с
1, и умножай его на каждое число от2доn. Начало с 1 также даёт правильный ответ для0и1.
Решение
У факториала есть два эквивалентных описания, и каждое из них можно превратить в код. Как произведение: n! = 1 × 2 × ... × n — это цикл. Как рекурсивное определение: 0! = 1 и n! = n × (n-1)! — это функция, которая вызывает саму себя. В обоих случаях выполняется около n умножений. Завершить стоит циклом, потому что ему не нужен стек вызовов.
Рекурсия из определения
Идея
Факториал определяется через меньший факториал: n! = n × (n-1)!. Если ты уже знаешь, что 4! = 24, то 5! = 5 × 24 = 120. Рекурсивная функция записывает это предложение в виде кода. Чтобы получить factorial(n), она запрашивает factorial(n-1) и умножает ответ на n.
Для вызовов нужно место остановки — базовый случай: factorial(0) возвращает 1, ничего не вызывая. Каждый вызов уменьшает n на единицу, поэтому при значении 5 вызовы идут так: 5, 4, 3, 2, 1, 0. Затем ответы возвращаются по цепочке: 1, 1, 2, 6, 24, 120.
Всего выполняется n + 1 вызовов и n умножений, поэтому время работы составляет O(n). Каждый вызов ждёт в стеке, пока не вернётся вызов ниже, поэтому стек содержит n + 1 кадров, что требует O(n) памяти. При n ≤ 12 это совсем немного, но тот же подход на большом входном значении переполняет стек.
Алгоритм
- Если
nравно0, верните1. Это базовый случай. - В противном случае вызовите функцию для
n-1. - Умножьте этот результат на
nи верните его.
def factorial(n):
if n == 0:
return 1 # base case: 0! = 1
return n * factorial(n - 1)Умножение в цикле
Идея
Разверните рекурсию — и получите накапливаемое произведение. Начните с result = 1 и умножайте его на 2, затем на 3 и так далее до n. Для n = 5 результат будет таким: 1, 2, 6, 24, 120.
Начало с 1 подходит и для наименьших входных значений. При n = 0 и n = 1 цикл от 2 до n выполняется ноль раз, и функция возвращает начальное значение 1, которое является правильным ответом в обоих случаях.
Цикл выполняет n-1 умножений, работает за время O(n) и хранит одно число, используя O(1) памяти. Здесь нет стека вызовов, который мог бы переполниться, поэтому интервьюеры ожидают увидеть эту версию после того, как вы показали рекурсивный вариант.
Алгоритм
- Установи
result = 1. - Перебери
kот2доnвключительно. - На каждом шаге умножай
resultнаk. - Верни
result.
def factorial(n):
result = 1
for k in range(2, n + 1):
result *= k
return result
Ловушки и крайние случаи
Код вычисления факториала короткий, поэтому ошибки скрываются в граничных случаях.
- Начинать произведение с
0. При каждом умножении оно остаётся равным 0. Начальное значение произведения —1. - Останавливать рекурсию только при
n == 1. При вызове с0функция никогда не достигает базового случая: она продолжает переходить к -1, -2 и так далее, пока не переполнится стек. Сделайтеn == 0базовым случаем. - Использовать в цикле
k < nвместоk ≤ n. При этом пропускается последний множитель, и возвращается(n-1)!, поэтому для5результатом будет 24 вместо 120. - Игнорировать переполнение.
13! = 6227020800не помещается в знаковое 32-битное целое число. В Java и C# произведение незаметно циклически переходит к неправильному числу, в C знаковое переполнение приводит к неопределённому поведению, а отладочная сборка Rust вызывает панику. 64-битное целое число вмещает до20!; для больших значений нужны большие целые числа. - В Swift писать
for k in 2...n. Замкнутый диапазон, конец которого меньше начала, приводит к сбою во время выполнения, еслиnравно 0 или 1.
Частые вопросы4
Какова временная сложность вычисления факториала?
И цикл, и рекурсия выполняют одно умножение для каждого числа вплоть до n, поэтому время составляет O(n). Циклу требуется дополнительное пространство O(1). Рекурсия сохраняет один кадр стека для каждого вызова до возврата базового случая, поэтому использует пространство O(n).
Почему 0! равно 1?
0! — это произведение без множителей, а произведение без множителей равно 1, так же как сумма без слагаемых равна 0. Благодаря этому правило n! = n × (n-1)! остаётся верным при n = 1: 1! = 1 × 0! = 1. Подсчёт тоже это подтверждает: существует ровно один способ упорядочить ноль предметов.
Что лучше для вычисления факториала: рекурсия или цикл?
Они выполняют одни и те же умножения и возвращают один и тот же результат. Рекурсивный вариант читается как математическое определение, поэтому это классическое первое упражнение по рекурсии. Цикл использует постоянный объём памяти и не может переполнить стек вызовов, поэтому в реальном коде он предпочтительнее.
Какой наибольший факториал помещается в целое число?
12! = 479001600 — наибольший факториал, который помещается в знаковое 32-битное целое число. 20! = 2432902008176640000 — наибольший факториал для знакового 64-битного целого числа. Для больших значений нужны числа неограниченного размера, такие как int в Python, BigInteger в Java или BigInt в JavaScript.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def factorial(n):
# Напишите код здесьСлучай 1
Случай 2
Ввод
n = 5
Ожидается
120