Примеры решений прототипа №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])