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

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

Рекурсия

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

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

6142

Пояснение

Решение:

Число 23 нечётное, поэтому $F(23) = 2 + 2 \cdot F(21)$ . Нечётная ветка уменьшает аргумент сразу на 2, значит вся цепочка идёт только по нечётным числам, и формула для чётных $n$ не понадобится вовсе.

База: $F(1) = 1$ . Далее каждый раз удваиваем предыдущее значение и прибавляем 2:

$n$	$F(n)$
1	1
3	4
5	10
7	22
9	46
11	94
13	190
15	382
17	766
19	1534
21	3070
23	6142

Здесь $F(3) = 2 + 2 \cdot 1 = 4$ , $F(5) = 2 + 2 \cdot 4 = 10$ и так далее.

Можно заметить закономерность: величина $F(n) + 2$ на каждом шаге удваивается, поэтому $F(2k + 1) = 3 \cdot 2^{k} - 2$ . При $k = 11$ получаем $3 \cdot 2048 - 2 = 6142$ .

import sys
sys.setrecursionlimit(10000)

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

print(F(23))   # 6142

Ответ: 6142