Задание 16 ЕГЭ: функция G, растущая до порога

Две функции: G идёт вверх до порога. Тема номера — рекурсивные функции. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

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

F(n) = 7 при n < 8;
F(n) = F(n − 1) + G(n) при n ≥ 8;
G(n) = n при n ≥ 2139;
G(n) = G(n + 1) + 6 при n < 2139.

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

Решение

G(n) поднимается шагами по 1, пока аргумент не станет не меньше 2139; за каждый шаг добавляется 6. Если шагов j = ⌈(2139 − n) / 1⌉, то G(n) = n + j·1 + j·6. F(316) — это 7 плюс сумма G(n) при n от 8 до 316. Рекурсия «вверх» глубиной в тысячи вызовов в Python падает, поэтому считаем в цикле: G — от порога вниз, F — снизу вверх.

g = {}
for n in range(2139 + 1, 0, -1):
    g[n] = n if n >= 2139 else g[n + 1] + 6
f = {}
for n in range(1, 316 + 1):
    f[n] = 7 if n < 8 else f.get(n - 1, 7) + g[n]
print(f[316])

Ответ: 4326316.

Решить такую задачу — новый вариант с проверкой