16 номер. Рекурсия
Вычисление рекурсивной функции
(Р. Косов) Алгоритм вычисления функций F(n) и G(n), где n - целое число, задан следующими соотношениями:
F(n)= F(n-5) + 1092, если n ≥ 128;
F(n) = 5 × G(n-7) + 29,, если n < 128;
G(n) = n - 15, если n > 303 728;
G(n) = G(n + 8)/2 - 109, если n ≤ 303 728.
Чему равно значение функции F(2049)?
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
from functools import * @lru_cache(None)def f(n): if n >= 128: return f(n-5) + 1092 else: return 5 * g(n-7) + 29 @lru_cache(None)def g(n): if n > 303728: return n - 15 else: return g(n+8) / 2 - 109 for i in reversed(range(301210)): g(i) for i in range(55000): f(i) print(f(2049))