Задание 16. Информатика. 2023-4

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

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

Чему равно значение функции \(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:
        return F(n-1) - F(n-2)
    t = 0
    for i in range(1, n):
        t += F(i)
    return t

print(F(39))

Ответ: \(41518080\)