Математические алгоритмы: факториал числа в языке Python

Раздел: Основы Python -> Математические алгоритмы

Вычисление факториала числа в Python

Факториал натурального числа n (обозначается n!) - это произведение всех натуральных чисел от 1 до n. Для n=0 по определению 0!=1. В Python существует несколько способов вычисления факториала, от простых циклов до встроенных функций.

Самый эффективный ручной алгоритм: итеративный цикл for


def factorial_iterative(n):
    if n < 0:
        raise ValueError('Факториал определён только для неотрицательных чисел')
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iterative(5))  # 120

число является простым python (проверка числа на простоту в python)

Этот метод требует O(n) времени и O(1) дополнительной памяти. Он оптимален для ручной реализации, так как не создаёт рекурсивных вызовов и использует минимум операций.

Как вычислить факториал с помощью рекурсии?


def factorial_recursive(n):
    if n < 0:
        raise ValueError('Факториал определён только для неотрицательных чисел')
    if n in (0, 1):
        return 1
    return n * factorial_recursive(n - 1)

print(factorial_recursive(5))  # 120

Python факториал числа (вычисление факториала числа в python)

Рекурсивный вариант лаконичен, но имеет ограничение по глубине рекурсии (по умолчанию 1000). Каждый вызов создаёт новый фрейм, что приводит к большему расходу памяти по сравнению с итеративным методом.

Возможные проблемы:

RecursionError для n больше 1000 (можно увеличить лимит sys.setrecursionlimit()).
Рекурсия - не самый быстрый способ из-за накладных расходов на вызовы.
При отрицательном n выбросится ValueError, который нужно обрабатывать.

Как использовать встроенную функцию math.factorial?


import math
print(math.factorial(5))  # 120

числа фибоначчи python (числа фибоначчи в python)

Это наиболее эффективное решение для всех практических задач, так как math.factorial реализована на C. Функция принимает только целые неотрицательные числа. Для дробных аргументов применяется math.gamma(n+1).

Типичные ошибки:

ValueError при отрицательном аргументе.
TypeError для нецелых чисел (например, 5.5).

Как вычислить факториал через reduce из functools?


from functools import reduce
import operator

def factorial_reduce(n):
    if n < 0:
        raise ValueError('Факториал определён только для неотрицательных чисел')
    if n == 0:
        return 1
    return reduce(operator.mul, range(1, n + 1))

print(factorial_reduce(5))  # 120

Reduce последовательно применяет оператор умножения ко всем элементам диапазона. Этот подход менее читаем, но демонстрирует функциональный стиль. Производительность близка к итеративному циклу.

Как ускорить рекурсию с помощью кеширования (мемоизации)?


from functools import lru_cache

@lru_cache(maxsize=None)
def factorial_memo(n):
    if n < 0:
        raise ValueError('Факториал определён только для неотрицательных чисел')
    if n in (0, 1):
        return 1
    return n * factorial_memo(n - 1)

print(factorial_memo(5))  # 120

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

Замечание:

Кеширование полезно, если факториал одного и того же числа вызывается многократно. Без декоратора рекурсия будет пересчитывать все значения заново.

Как записать факториал через цикл while?


def factorial_while(n):
    if n < 0:
        raise ValueError('Факториал определён только для неотрицательных чисел')
    result = 1
    i = 2
    while i <= n:
        result *= i
        i += 1
    return result

print(factorial_while(5))  # 120

Цикл while - альтернатива for, с тем же числом операций. Выбор между for и while зависит от личных предпочтений; for обычно короче для последовательных чисел.

Общие проблемы и ошибки при вычислении факториала

Переполнение стека: при использовании рекурсии для больших n. Решение - итеративный метод или увеличение лимита рекурсии.
Тип аргумента: факториал определён только для целых неотрицательных чисел. Для float, complex, отрицательных выбрасывается исключение. Следует проверять входные данные.
Большие числа: Python поддерживает целые произвольной длины, но факториал очень больших чисел (n>10000) может потребовать много времени и памяти. Для таких случаев используйте math.factorial, оптимизированный на C.
Логические ошибки: забыть обработать случай n=0, который должен вернуть 1. Рекомендуется всегда проверять граничные условия.

Расширенные примеры и нестандартные подходы

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

Вычисление факториала для больших чисел (n=1000)

Пример


import math
n = 1000
fact = math.factorial(n)
digits = len(str(fact))
print(f'Факториал {n}! содержит {digits} цифр')

Факториал 1000! содержит 2568 цифр

Сравнение производительности итеративного и рекурсивного методов

Пример


import timeit

def iter_fact(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

def rec_fact(n):
    if n in (0,1):
        return 1
    return n * rec_fact(n-1)

n = 500
time_iter = timeit.timeit(lambda: iter_fact(n), number=1000)
time_rec = timeit.timeit(lambda: rec_fact(n), number=1000)
print(f'Итеративный: {time_iter:.5f} сек, рекурсивный: {time_rec:.5f} сек')

Итеративный: 0.00123 сек, рекурсивный: 0.04234 сек

Использование math.prod (Python 3.8+)

Пример


import math

def factorial_prod(n):
    if n < 0:
        raise ValueError('Факториал только для неотрицательных')
    if n == 0:
        return 1
    return math.prod(range(1, n+1))

print(factorial_prod(10))  # 3628800

Вычисление двойного факториала (n!!)

Пример


def double_factorial(n):
    if n < 0:
        raise ValueError
    if n in (0,1):
        return 1
    result = 1
    start = 2 if n % 2 == 0 else 1
    for i in range(start, n+1, 2):
        result *= i
    return result

print(double_factorial(5))  # 5!! = 5*3*1 = 15
print(double_factorial(6))  # 6!! = 6*4*2 = 48

15
48

Применение декоратора lru_cache для многократных вызовов

Пример


from functools import lru_cache

@lru_cache(maxsize=None)
def fact(n):
    if n in (0,1):
        return 1
    return n * fact(n-1)

# Первый вызов – вычисление
print(fact(100))
# Второй вызов – мгновенный результат из кеша
print(fact(100))

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Вычисление факториала через рекурсию с хвостовой рекурсией (имитация)

Пример


def tail_fact(n, acc=1):
    if n == 0:
        return acc
    return tail_fact(n-1, acc * n)

print(tail_fact(5))  # 120

Замечание:

Python не оптимизирует хвостовую рекурсию, поэтому при больших n это приведёт к Stack Overflow. Данный пример просто иллюстрирует идею.

Обработка ошибок при вводе нецелого числа

Пример


def safe_factorial(n):
    if not isinstance(n, int) or isinstance(n, bool):
        raise TypeError('Аргумент должен быть целым числом')
    if n < 0:
        raise ValueError('Аргумент должен быть неотрицательным')
    if n == 0:
        return 1
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

try:
    print(safe_factorial(5.5))
except TypeError as e:
    print(e)  # Аргумент должен быть целым числом

Аргумент должен быть целым числом

Вычисление факториала числа в Python - comments

Python факториал числа (python)