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

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

Рекурсия

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

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

78731

Пояснение

Решение:

Здесь нужны обе ветки: чётная опирается на $F(n - 1)$ , а нечётная — сразу на $F(n - 1)$ и $F(n - 2)$ . Поэтому удобно считать значения подряд, снизу вверх, начиная с базы $F(1) = 1$ .

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

$n$	$F(n)$
1	1
2	3
3	7
4	11
5	29
6	35
7	99
8	107
9	313
10	323
11	959
12	971
13	2901
14	2915
15	8731
16	8747
17	26225
18	26243
19	78711
20	78731

Проверим первые шаги: $F(2) = 2 + F(1) = 3$ , $F(3) = 2 \cdot 3 + 1 = 7$ , $F(4) = 4 + 7 = 11$ , $F(5) = 2 \cdot 11 + 7 = 29$ . Последний шаг: $F(20) = 20 + F(19) = 20 + 78711 = 78731$ .

import sys
sys.setrecursionlimit(10000)

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

print(F(20))   # 78731

Ответ: 78731