Задание 16 № 13529: Вычисление значения рекурсивной функции — ЕГЭ по информатике

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

$F(n) = 1 \, \text{при} \, n < 3;$

$F(n) = F(n-1) - F(n-2), \, \text{если} \, n > 2 \, \text{и при этом} \, n \, \text{нечётно};$

$F(n) = \sum_{i=1}^{n-1} F(i), \, \text{если} \, n > 2 \, \text{и при этом} \, n \, \text{чётно}.$

Чему равно значение функции $F(39)$ ?

Решение:

Решение на Python:

from functools import lru_cache

@lru_cache(None)
def f(n):
    if n < 3: return 1
    if n > 2 and n % 2 != 0: return f(n-1)-f(n-2)
    else: return sum(f(i) for i in range(1, n))

for n in range(1, 100):
    f(n)
print(f(39))

Ответ: 41518080

Ответ:

41518080