Задание №16 — Рекурсия
#69283Задание №16ФИПИ
Рекурсия
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n — чётно;
F(n) = 2 × F(n − 2), если n > 1 и при этом n — нечётно.
Чему равно значение функции F(26)?
Правильный ответ
4122
Пояснение
Решение:
Число 26 чётное, поэтому . Осталось найти .
Для нечётных правило уменьшает аргумент на 2, оставляя его нечётным, поэтому цепочка идёт только по нечётным числам: (от 25 до 1 ровно 12 шагов). Значит .
Итого .
from functools import lru_cache
@lru_cache(None)
def F(n):
if n == 1:
return 1
if n % 2 == 0:
return n + F(n - 1)
return 2 * F(n - 2)
print(F(26)) # 4122Ответ: 4122