Задание 16 ЕГЭ: две функции F и G

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

Пример

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

F(n) = 5 × G(n − 4) − 7;
G(n) = n + 7, если n ≤ 25;
G(n) = G(n − 5) + 5, если n > 25.

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

Решение

F не рекурсивна: F(11840) = 5 · G(11836) − 7. G спускается с шагом 5: 11836 → 11831 → … пока аргумент больше 25. Спуск закончится на 21 (это первое число, не большее 25, с тем же остатком при делении на 5), шагов (11836 − 21) / 5 = 2363, каждый прибавляет 5. G(21) = 28, G(11836) = 28 + 11815 = 11843, F(11840) = 5 · 11843 − 7 = 59208. Не забудьте внешнюю формулу F — G(…) ещё не ответ.

Проверим программой без глубокой рекурсии (на Windows она падает даже с увеличенным sys.setrecursionlimit): значения считаем в цикле в том порядке, в котором они нужны.

G = {}
for n in range(1, 11837):  # снизу вверх: G(n) зависит от G(n − 5)
    if n <= 25:
        G[n] = n + 7
    else:
        G[n] = G[n - 5] + 5

print(5 * G[11840 - 4] - 7)

Ответ: 59208.

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