Задание 16 ЕГЭ по информатике

С несколькими методами решения 16 заданий первого типа мы уже познакомились еще в прошлой статье. Чаще всего применяются такие методы: Задания второго типа мы будем решать именно последним методом — с использованием декоратора @lru_cache. Вспомним, чем отличается второй тип: здесь нам предстоит работать не с одной, а сразу с двумя функциями. Вы, конечно, можете решать такие задания вручную, но это займёт гораздо больше времени, чем написание программного кода с кешированием. Освежим в памяти алгоритм...

В прошлых статьях мы уже познакомились с работой рекурсивных функций в языке Python, с ограничением на глубину рекурсии и научились оптимизировать наши функции с помощью механизма мемоизации. Теперь можем смело перейти к разбору алгоритма решения 16 заданий ЕГЭ по информатике. Как уже было сказано ранее, в данных заданиях нам предстоит вычислить результат некоторого выражения, включающего в себя одну или две рекурсивные функции. И как раз по количеству этих функций мы и будем типизировать эти задания: Именно количество функций и скажется на нашем решении...

В прошлой статье мы разобрались, что такое рекурсия и как она работает в Python. Мы узнали, что рекурсия — это когда функция вызывает сама себя, разбивая большую задачу на более мелкие подзадачи. Познакомились со стеком вызовов — специальным местом в памяти, где хранится информация о каждом вызове функции. А ещё выяснили, что в Python есть ограничение на глубину рекурсии — по умолчанию 1000 вызовов. Мы научились обходить это ограничение с помощью setrecursionlimit(), но поняли, что это опасно: можно получить ошибки Segmentation Fault или Out of Memory...

Скоро мы начнём разбирать алгоритм решения 16 задания ЕГЭ по информатике. Это задание проверяет ваше умение работать с рекурсивными алгоритмами — вам дают функцию, заданную через саму себя, и просят вычислить её значение. Звучит странно? Сейчас разберёмся, что это вообще такое и как с этим работать. Но, прежде чем переходить к решению конкретных задач, нужно понять, как Python воспринимает рекурсию, почему иногда программа падает с ошибкой и что с этим делать. Именно об этом и поговорим в данной статье...