16.01 Одна функция

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: , , , при : . Выведем ответ вызовом функции

Рекурсивное решение

def f(n):
    # База для n = 1, n = 2 и n = 3
    if n == 1:
        return 0
    if n == 2 or n == 3:
        return 1
    # Рекуррентная формула
    return f(n - 1) + n * n + f(n - 2)

print(f(19))

Динамическое решение

Для динамического решения создадим список, где каждому i-тому элементу будет соответствовать . Заполним список по правилам из условия и выведем ответ вызовом 19-го элемента.

# Массив для хранения значений F
f = [0] * (19 + 1)
# База для n = 1, n = 2 и n = 3
f[1] = 0
f[2] = 1
f[3] = 1
# Рекуррентно вычисляем
for i in range(4, 19 + 1):
    f[i] = f[i - 1] + i * i + f[i - 2]

print(f[19])