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

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

Рекурсия

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

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

49197

Пояснение

Решение:

Нечётная ветка использует сразу два предыдущих значения, поэтому считаем таблицу подряд, начиная с базы $F(1) = 1$ .

Правила: при чётном $n$ берём $F(n) = n + F(n - 1)$ ; при нечётном $n \gt 1$ берём $F(n) = F(n - 1) + 2 F(n - 2)$ .

$n$	$F(n)$
1	1
2	3
3	5
4	9
5	19
6	25
7	63
8	71
9	197
10	207
11	601
12	613
13	1815
14	1829
15	5459
16	5475
17	16393
18	16411
19	49197

Проверим первые шаги: $F(2) = 2 + 1 = 3$ , $F(3) = 3 + 2 \cdot 1 = 5$ , $F(4) = 4 + 5 = 9$ , $F(5) = 9 + 2 \cdot 5 = 19$ . Последний шаг: $F(19) = F(18) + 2 F(17) = 16411 + 2 \cdot 16393 = 49197$ .

import sys
sys.setrecursionlimit(10000)

def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return n + F(n - 1)
    return F(n - 1) + 2 * F(n - 2)

print(F(19))   # 49197

Ответ: 49197