Алгоритм вычисления значения функции , где n — натуральное число, задан следующими соотношениями: при n = 1; если n 1 и при этом n нечётно, если n 1 и при этом n чётно. Чему равно значение функции ?

Задание 16 № 23384: Вычисление значения рекурсивной функции — ЕГЭ по информатике

Алгоритм вычисления значения функции $F(n)$ , где n — натуральное число, задан следующими соотношениями:

$F(n) = 1$ при n = 1;

$F(n) = 3 × n + F(n − 2)$ если n > 1 и при этом n нечётно,

$F(n) = 4 × F(n / 2)$ если n > 1 и при этом n чётно.

Чему равно значение функции $F(42)$ ?

Решение:

Решение на Python:

from functools import lru_cache

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

for i in range(1, 43):
    F(i)
print(F(42))

Ответ: 1444

Ответ:

1444

Источник: ЕГЭ · Информатика · Апробация 2022