Задачи на функции в языке Python - факториал
Задачи на функции в Python: вычисление факториала
Функции в Python помогают организовать код и решать повторяющиеся задачи. Рассмотрим классическую задачу вычисления факториала числа и различные способы её реализации. Факториал числа n (обозначается n!) определяется как произведение всех целых чисел от 1 до n, причём 0! = 1.
Как эффективно вычислить факториал без рекурсии?
Самое простое и эффективное решение - итеративная функция. Она использует цикл for и одну переменную для накопления результата. Время выполнения O(n), память O(1).
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
print(factorial_iter(5)) # 120алгоритм решения задачи python (алгоритм решения задачи на python)
Пояснение: функция начинается с результата 1. Затем перебираются числа от 2 до n включительно. На каждом шаге текущее число умножается на result. При n = 0 цикл не выполняется, и возвращается 1.
Как решить задачу с помощью рекурсии?
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1)
print(factorial_rec(5)) # 120базовые задачи python (базовые задачи python)
Рекурсивная функция вызывает саму себя с уменьшенным аргументом, пока не достигнет базового случая (n == 0). Такой подход наглядно демонстрирует математическое определение факториала.
Цель использования: учебные примеры, демонстрация рекурсии, задачи с небольшими n.
Как использовать functools.reduce для факториала?
from functools import reduce
def factorial_reduce(n):
return reduce(lambda x, y: x * y, range(1, n + 1), 1)
print(factorial_reduce(5)) # 120задачи для обучения python (задачи для обучения python)
Функция reduce последовательно применяет лямбду к элементам последовательности, накапливая результат. Третьим аргументом передаётся начальное значение (1).
Случаи использования: когда требуется функциональный стиль или цепочка операций.
Как применить кэширование (lru_cache) для улучшения рекурсии?
from functools import lru_cache
@lru_cache(maxsize=None)
def factorial_cache(n):
if n == 0:
return 1
return n * factorial_cache(n - 1)
print(factorial_cache(5)) # 120задачи на классы в python (задачи на классы в python)
Декоратор lru_cache запоминает результаты уже вычисленных значений. При повторных вызовах с тем же аргументом значение берётся из кэша. Это не делает рекурсию глубже, но ускоряет многократные вызовы.
Как использовать встроенную функцию math.factorial?
import math
print(math.factorial(5)) # 120В Python уже есть готовая реализация факториала в модуле math. Она написана на C и максимально оптимизирована.
Случаи использования: продакшен, быстрые вычисления, когда не требуется кастомная логика.
Расширенные примеры работы с функциями для факториала
Вычисление факториала для списка чисел с помощью map
import math
numbers = [0, 1, 2, 5, 10]
factorials = list(map(math.factorial, numbers))
print(factorials)[1, 1, 2, 120, 3628800]
Пояснение: функция map применяет math.factorial к каждому элементу списка. Результат преобразуется в список.
Генератор последовательности факториалов
def factorial_gen(n):
result = 1
for i in range(1, n + 1):
result *= i
yield result
for val in factorial_gen(5):
print(val, end=' ')1 2 6 24 120
Генератор yield выдаёт факториалы по одному, не храня весь список в памяти.
Мемоизация вручную через словарь
fact_cache = {0: 1}
def factorial_memo(n):
if n not in fact_cache:
fact_cache[n] = n * factorial_memo(n - 1)
return fact_cache[n]
print(factorial_memo(7)) # 5040
print(fact_cache) # словарь с промежуточными результатами5040
{0: 1, 1: 1, 2: 2, 3: 6, 4: 24, 5: 120, 6: 720, 7: 5040}
Пояснение: функция проверяет наличие ключа в словаре. Если его нет - рекурсивно вычисляет и сохраняет. Это аналог lru_cache, написанный вручную.
Функция высшего порядка: возврат функции для вычисления факториала
def make_factorial():
def factorial(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
return factorial
fact = make_factorial()
print(fact(6)) # 720Замыкание make_factorial создаёт новую функцию factorial, которая может быть использована многократно.
Рекурсия с хвостовой рекурсией (имитация через аккумулятор)
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, acc * n)
print(factorial_tail(5)) # 120Внимание: Python не оптимизирует хвостовую рекурсию, поэтому это лишь стилистический приём для упрощения кода, но глубина стека не уменьшается.
Комбинирование функций: факториал через лямбду и reduce
from functools import reduce
factorial_lambda = lambda n: reduce(lambda x, y: x * y, range(1, n + 1), 1)
print(factorial_lambda(10)) # 3628800Анонимная функция присваивается переменной, что не рекомендуется по PEP 8, но демонстрирует возможности.