16.02 Две функции

Идея рекурсивного решения:

Для вычисления нужно уметь находить . Функция задана рекурсивно:

Её реализуем как рекурсивную функцию g(n). Чтобы не пересчитывать одни и те же значения, используем мемоизацию (lru_cache). Функция вычисляется через , поэтому достаточно вызвать f(15548).

Решение через рекурсию:

from functools import lru_cache

# Рекурсивная функция g с мемоизацией
@lru_cache(None)
def g(n):
    if n < 10:
        return 2 * n
    return g(n - 2) + 1

# Функция f через g
@lru_cache(None)
def f(n):
    return 2 * (g(n - 3) + 8)

# Выгружаем сначала в память значения функции от 1 до 15548
for i in range(15549):
    f(i)

# Вычисление результата
print(f(15548))

Идея динамического решения:

Заведём массив g и последовательно вычислим его значения: для положим , а для используем формулу . После этого в массив f заполним значения по формуле . Такой способ удобен, так как каждое значение считается один раз и легко получить .

Решение через динамику:

g = [0] * 16000
f = [0] * 16000

# Заполнение значений g
for n in range(16000):
    if n < 10:
        g[n] = 2 * n
    else:
        g[n] = g[n - 2] + 1

# Вычисление значений f
for n in range(16000):
    f[n] = 2 * (g[n - 3] + 8)

print(f[15548])