Номер 16. ЕГЭ по информатике

# Способ 1 - рекурсия без мемоизации (самый медленный)
def f(n):
    if n < 5:
        return n
    return 2 * n * f(n - 4)

print((f(13766) - 9 * f(13762)) // f(13758))

# Способ 2 - мемоизация с lru_cache
from functools import lru_cache

@lru_cache(None)
def f(n):
    if n < 5:
        return n
    return 2 * n * f(n - 4)

print((f(13766) - 9 * f(13762)) // f(13758))

# Способ 3 - мемоизация через словарь
def f(n, cache={}):
    if n in cache:
        return cache[n]
    if n < 5:
        cache[n] = n
    else:
        cache[n] = 2 * n * f(n - 4, cache)
    return cache[n]

print((f(13766) - 9 * f(13762)) // f(13758))

# Способ 4 - использование декоратора
def memoize(func):
    cache = {}
    def wrapper(n):
        if n in cache:
            return cache[n]
        cache[n] = func(n)
        return cache[n]
    return wrapper

@memoize
def f(n):
    if n < 5:
        return n
    return 2 * n * f(n - 4)

print((f(13766) - 9 * f(13762)) // f(13758))

# Способ 5 - использование @cache (Python 3.9+)
from functools import cache

@cache
def f(n):
    if n < 5:
        return n
    return 2 * n * f(n - 4)

print((f(13766) - 9 * f(13762)) // f(13758))

---

Это самые популярные и простые способы мемоизации — все функции названы просто f. Вы можете выбрать любой из вариантов или вставить их все по порядку для тестирования!