К списку задач
ЕГЭ 16 · Рекуррентные выражения
Вычисление рекурсивной функции
Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(n) = n при n < 3; ; F(n) = F(n - 1) + F(n - 2) + 1, если n > 2 и при этом n нечётно;; F(n) = Σi=1n-1F(i), если n > 2 и при этом n чётно.
Чему равно значение функции F(38)?
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Разбор
from functools import lru_cache @lru_cache(None)def f(n): if n < 3: return n if n > 2 and n % 2 == 1: return f(n-1) + f(n-2) + 1 if n > 2 and n % 2 == 0: sum_ = 0 for i in range(1, (n-1)+1): sum_ += f(i) return sum_ print(f(38))