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

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

Рекурсия

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

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

987

Пояснение

Решение:

Число 35 нечётное, поэтому работает третья строка определения, а она уменьшает аргумент сразу на 2. Значит вся цепочка вычислений идёт по нечётным числам, и формула для чётных $n$ вообще не используется. Упростим нечётную ветку:

$F(n) = 3(n + 1) + F(n - 2) - 2 = 3n + 1 + F(n - 2), \quad n \text{ — нечётное}, \; n \gt 2.$

База — $F(1) = 1$ . Идём вверх шагами по 2:

$n$	$F(n)$
1	1
3	11
5	27
7	49
9	77
11	111
13	151
15	197
17	249
19	307
21	371
23	441
25	517
27	599
29	687
31	781
33	881
35	987

Например, $F(3) = 3 \cdot 3 + 1 + F(1) = 10 + 1 = 11$ , а последний шаг: $F(35) = 3 \cdot 35 + 1 + F(33) = 106 + 881 = 987$ .

import sys
sys.setrecursionlimit(10000)

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

print(F(35))   # 987

Ответ: 987