Примеры решений прототипа №1

Примеры решения

№ 5133 /dev/inf 11.22 (Уровень: Базовый)

(А. Рогов) Алгоритм вычисления значения функции F(n)F(n), где nn – натуральное число, задан следующими соотношениями:

$F(n)=1$ при $n<3$;
$F(n)=F(n-1)+n-1$ если $n > 2$ и при этом $n$ чётно;
$F(n)=F(n-2)+2n-2$, если $n > 2$ и при этом $n$ нечётно.

Чему равно значение выражения $F(2048)-F(2045)$?

# Решение рекурсией
from functools import cache

@cache
def f(n):
    if n < 3: return 1
    if n > 2 and n % 2 == 0: return f(n - 1) + n - 1
    return f(n - 2) + 2 * n - 2
for i in range(2049): f(i)
print(f(2048) - f(2045))

# Решение динамическим программированием
f = {}
for n in range(2050):
    if n < 3: f[n]=1
    elif n > 2 and n % 2 == 0: f[n] = f[n - 1] + n - 1
    else: f[n] = f[n - 2] + 2 * n - 2
print(f[2048] - f[2045])