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

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

Рекурсия

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

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

2214271

Пояснение

Решение:

Сначала найдём $F(2)$ , которое входит в правило для нечётных $n$ : число 2 чётное и $2 \gt 1$ , поэтому $F(2) = 3 \cdot F(1) = 3$ . Значит при нечётном $n \gt 1$ правило принимает вид $F(n) = 5n + F(n-1) + 3$ .

Каждое значение зависит только от предыдущего, поэтому просто идём по возрастанию $n$ :

$F(1) = 1$ , $F(2) = 3 \cdot 1 = 3$ , $F(3) = 5 \cdot 3 + 3 + 3 = 21$ , $F(4) = 3 \cdot 21 = 63$ , $F(5) = 5 \cdot 5 + 63 + 3 = 91$ , $F(6) = 3 \cdot 91 = 273$ и так далее.

n	F(n)
1	1
2	3
3	21
4	63
5	91
6	273
7	311
8	933
9	981
10	2943
11	3001
12	9003
13	9071
14	27213
15	27291
16	81873
17	81961
18	245883
19	245981
20	737943
21	738051
22	2214153
23	2214271

Последний шаг: $F(23) = 5 \cdot 23 + F(22) + 3 = 115 + 2214153 + 3 = 2214271$ .

from functools import lru_cache

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

print(F(23))   # 2214271

Ответ: 2214271