Задание №16 — Рекурсия

#69536Задание №16ФИПИ

Рекурсия

Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями:
F(n) = 1, если n <= 1;
F(n) = $3 + F ( n - 1 ) \cdot F ( n - 2 ) - F ( n - 1 ) - F ( n - 2 ) ,$ если n > 1 и при этом n нечётно;
F(n) = $2 \cdot F ( n - 1 ) ,$ если n > 1 и при этом n чётно.
Чему равно значение функции F(12)?

Правильный ответ

30830260

Пояснение

Решение:

Значения считаем по порядку, начиная с $F(0) = F(1) = 1$ . Для чётных $n \gt 1$ значение просто удваивается, для нечётных используем $F(n) = 3 + F(n-1) \cdot F(n-2) - F(n-1) - F(n-2)$ (удобно свернуть его как $F(n) = \bigl(F(n-1) - 1\bigr)\bigl(F(n-2) - 1\bigr) + 2$ ).

$F(2) = 2 \cdot 1 = 2$ ; $F(3) = 3 + 2 \cdot 1 - 2 - 1 = 2$ ; $F(4) = 2 \cdot 2 = 4$ ; $F(5) = 3 + 4 \cdot 2 - 4 - 2 = 5$ ; $F(6) = 10$ ; $F(7) = 3 + 10 \cdot 5 - 10 - 5 = 38$ ; $F(8) = 76$ ; $F(9) = 3 + 76 \cdot 38 - 76 - 38 = 2777$ ; $F(10) = 5554$ ; $F(11) = 3 + 5554 \cdot 2777 - 5554 - 2777 = 15415130$ ; $F(12) = 2 \cdot 15415130 = 30830260$ .

n	F(n)
0	1
1	1
2	2
3	2
4	4
5	5
6	10
7	38
8	76
9	2777
10	5554
11	15415130
12	30830260

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n <= 1:
        return 1
    if n % 2 == 1:
        return 3 + F(n - 1) * F(n - 2) - F(n - 1) - F(n - 2)
    return 2 * F(n - 1)

print(F(12))   # 30830260

Ответ: 30830260