Разбор номера 25355 #kege по информатике #ЕГЭ16

Автор: ЕГКР 13.12.20
Уровень: Средний

Условие задачи:

Алгоритм вычисления функций F(n) и G(n), где n - целое число, задан следующими соотношениями:
F(n) = F(n−4)+3580, если n ≥ 19;
F(n) = 6×(G(n−7)−36), если n < 19;
G(n) = n/20+28, если n ≥ 248045;
G(n) = G(n+9)−4, если n < 248045.
Чему равно значение функции F(673)?

Теоретическая справка:

Такую задачу не получится решить просто импортируя sys.setrecursionlimit(), поэтому можно решать через списки, либо же через КЭШИРОВАНИЕ.

Код решения:

Ответ: 47

Комментарии к коду:

1. from functools import *
   Импортируем инструменты из functools (в т.ч. lru_cache).
2. def F(n):
   Определяем функцию F, принимает целое число n.
3. if n >= 19:
   Проверяем ветку для больших n (база/переход для рекурсии в F).
4. return F(n - 4) + 3580
   Рекурсивно уменьшаем n на 4 и прибавляем 3580 к результату.
5. else:
   Ветка для случая, когда n < 19.
6. return 6 * (G(n - 7) - 36)
   Вызываем G(n-7), вычитаем 36, умножаем итог на 6 и возвращаем.
7. @lru_cache()
   Включаем кэширование результатов G(n), чтобы ускорить повторные вызовы.
8. def G(n):
   Определяем функцию G, принимает целое число n.
9. if n >= 248045:
   Проверяем базовый случай: при больших n рекурсия в G останавливается.
10. return n / 20 + 28
    Возвращаем значение по формуле для базового случая G.
11. else:
    Ветка для случая, когда n < 248045.
12. return G(n + 9) - 4
    Рекурсивно увеличиваем n на 9 и вычитаем 4 из результата.
13. for i in range(248045, 0, -1):
    Цикл перебирает i от 248045 до 1 с шагом -1.
14. G(i)
    Заполняем кэш значениями G(i) для всех i в этом диапазоне.
15. print(F(673))
    Вычисляем F(673) (внутри будет использоваться G) и выводим результат.

Больше разборов на эту и другие задачи вы можете найти в нашем Телеграм канале: Информатика ЕГЭ | itpy 👨‍💻

Подписывайтесь на наш канал по теории Python: Азим вкатывается в IT | itpy 💻  Вы найдете тут много полезного!