Задание 16

Рекурсивные функции

Типов: 2

Как распознать

Рекурсия имеет огромный аргумент и шаг 3.

Условие

Вычислить выражение из F(247563), F(247560), F(247557).

Разбор

Иди снизу вверх и держи в кэше только последние значения.

Шаблон

from functools import lru_cache
@lru_cache(100)
def f(n):
    if n< 10:return 1
    if n >= 10: return (n+3)*f(n-3)
for n in range(10,247564):
    if n == 247563: x1 = f(n)
    elif n == 247560: x2 = f(n)
    elif n == 247557:x3 = f(n)
    else: f(n)
print((x1//519-477*x2)//x3)

Как распознать

F уменьшает аргумент, G увеличивает его до базы.

Условие

Вычислить F(548) для взаимосвязанных функций.

Разбор

Сначала прогрей G сверху вниз, затем F снизу вверх.

Шаблон

from functools import lru_cache
@lru_cache(100)
def f(n):
    if n>=21:return f(n-8) + 1095
    if n<21:return 10 * (g(n-7)-36)
@lru_cache(100)
def g(n):
    if n>=22560:return n/23 + 33
    if n <22560:return g(n+11)-4
for n in range(22560,5,-1): g(n)
for n in range(21,549): f(n)
print(f(548))