О задании
В прошлых статьях мы уже познакомились с работой рекурсивных функций в языке Python, с ограничением на глубину рекурсии и научились оптимизировать наши функции с помощью механизма мемоизации.
Теперь можем смело перейти к разбору алгоритма решения 16 заданий ЕГЭ по информатике. Как уже было сказано ранее, в данных заданиях нам предстоит вычислить результат некоторого выражения, включающего в себя одну или две рекурсивные функции.
И как раз по количеству этих функций мы и будем типизировать эти задания:
- К заданию первого типа отнесём те, в которых работать будем только с одной функцией
- В заданиях второго типа от нас уже потребуется реализация сразу двух рекурсивных функций. Именно задачи такого типа чаще всего и попадаются на экзаменах в последнее время.
Именно количество функций и скажется на нашем решении. В остальном же решения заданий внутри одного типа практически не отличаются. Ну а решать задания первого типа мы будем сразу тремя способами: ручным методом, итеративным (то есть без рекурсии совсем) и с использованием декоратора @lru_cache. Метод с увеличением глубины рекурсии разбирать не будем — данный метод не всегда эффективно работает, да и отличается от обычного решения всего одной строкой.
Алгоритм решения
Ручное решение
Многие задания с экзаменов прошлых лет легко решаются ручным методом. Суть его заключается в буквальном вычислении значений функций и выявлении зависимостей между этими значениями.
Рассмотрим этот способ на примере задания с такой формулировкой:
«Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(n)=n, при n ≥ 2025;
F(n)= n · 2 + F(n+2), если n < 2025
Чему равно значение выражения F(82) — F(81)?»
Давайте анализировать имеющиеся соотношения. Сразу можно обратить внимание на два момента:
- Если n меньше 2025, функция вызывает себя с аргументом n + 2
- Значит, F(82) будет обращаться к F(84), F(86), F(88) и так далее по чётным числам. А F(81) будет обращаться к F(83), F(85), F(87) и так далее по нечётным.
И оба этих процесса в итоге дойдут до значений ≥ 2025, где функция просто равна аргументу. Следовательно, только на значении 2025 мы сможем остановиться в своих вычислениях.
К чему это: порой в этих заданиях встречаются выражения с делением. В таком случае можно через 2-3 последовательных вызовов дойти до того возможности сократить два вызова функции и оставить просто чистую арифметику. Здесь же не такой случай, и нам придётся выявить зависимость в результатах работы функций вплоть до числа 2025.
Давайте запишем цепочку вычислений для вызова F(82):
F(82) = 2·82 + F(84)
F(84) = 2·84 + F(86)
F(86) = 2·86 + F(88)
…
F(2024) = 2·2024 + F(2026)
Но F(2026) по условию это просто число 2026: F(2024) = 2·2024 + 2026. Теперь понятно, что F(82) — это сумма всех значений 2·n для четных n от 82 до 2024 и плюс конечное значение 2026.
Теперь подсчитаем, сколько всего будет таких чётных чисел между 82 и 2024. Это будет арифметическая прогрессия с первым членом 82, последним — 2024 и шагом 2.
Количество членов арифметической прогрессии можно вычислить по такой школьной формуле: n = (L – A) / d +1. Здесь:
- L — последний член
- A — первый член
- d — шаг прогрессии
В нашем случае получается так: n = (2024 – 82) / 2 + 1 = 972. То есть всего в этой последовательности будет 972 числа. Запомните это! Ну а значение функции F(82) можем записать так: F(82) = 2·(82 + 84 + 86 + … + 2024) + 2026.
Аналогично поступаем и с вызовом F(81). Это будут вызовы функции с нечётными числами:
F(81) = 2·81 + F(83)
F(83) = 2·83 + F(85)
…
F(2023) = 2·2023 + F(2025)
Так как 2025 ≥ 2025:
F(2025) = 2025
Получаем такую последовательность: 81, 83, 85, …, 2023. Всё по той же формуле вычисляем количество чисел в ней: n = (2023 – 81) / 2 + 1 = 972. И запишем значение вызова функции от числа 81: F(81) = 2·(81 + 83 + 85 + … + 2023) + 2025.
Осталось лишь записать разность двух вызовов и вычислить результат:
F(82) − F(81) = [2 · (82 + 84 + … + 2024) + 2026] — [2 · (81 + 83 + … + 2023) + 2025] = 2·[(82 + 84 + … + 2024) − (81 + 83 + … + 2023)] + (2026 − 2025).
Внимательно присмотримся к обеим арифметическим прогрессиям: разность соответствующих элементов составляет 1:
82 − 81 = 1
84 − 83 = 1
…
2024 − 2023 = 1
Всего таких пар 972, равно как и чисел в каждой последовательности. Следовательно, в квадратных скобках мы получаем число 972 (по единице с каждой пары). Подставим его в выражение:
F(82) − F(81) = 2 · 972 + (2026 − 2025) = 1944 + 1 = 1945.
Вот и всё, мы получили ответ на это задание — число 1945.
Итеративный подход
Если вы испытываете трудности в ручных решениях, то можно воспользоваться навыками программирования. К примеру, 16 задания можно решать вовсе без использования рекурсивных функций — через итеративный подход.
Кстати, замену рекурсии на итеративный подход мы уже разбирали в этой статье.
Главная идея такого подхода в том, что если значение функции зависит от соседних значений, то:
- Существует порядок, в котором их можно посчитать
- Каждое новое значение можно получить из уже известного
Отметим, что итеративный подход работает, если выполняется хотя бы одно из условий:
- F(n) выражается через F(n−1), F(n−2) и т.д.
Тогда считаем снизу вверх - F(n) выражается через F(n+1), F(n+2) и т.д.
Тогда считаем сверху вниз - В условии есть граница, после которой функция задана явно
Например: F(n) = n при n ≥ 2025
Как вы можете заметить, все эти три пункта подходят под большинство 16 заданий ЕГЭ. Первое, на что нужно посмотреть в условии — это место, где функция задана явно, без обращения к самой себе. Именно оно определяет стартовую точку.
Например, если написано F(1) = 1, значит, вычисления начинаются с n = 1 и дальше идут вверх. А если в условии сказано F(n) = n при n ≥ 2025, то вычисления начинаются с большого значения и дальше идут вниз.
Эта точка старта важнее любой формулы. Без нее рекурсия просто не сработает и итеративный алгоритм невозможен.
Рассмотрим ситуацию, когда F(n) зависит от предыдущего значения, к примеру, от F(n − 1). Типичный пример:
F(1) = 1
F(n) = 2 · n · F(n − 1), при n ≥ 2.
Нужно найти F(10).
Здесь все предельно логично. Чтобы найти F(2), нужно знать F(1). Чтобы найти F(3), нужно знать F(2). Значит, мы просто идем от 1 вверх, шаг за шагом.
В итеративном решении это выглядит так. Мы заводим переменную F и кладем в нее стартовое значение, то есть F(1). После этого запускаем цикл, в котором на каждом шаге пересчитываем F по формуле. Переменная F всегда хранит текущее значение функции, и нам не нужно помнить все предыдущие.
Такой цикл буквально повторяет математическую формулу, только вместо рекурсии используется присваивание. Именно поэтому он работает корректно.
Важно понимать, что здесь нет никакой оптимизации или трюка. Мы делаем ровно то же самое, что и рекурсивная функция, только вручную и по шагам. То есть такой алгоритм применим в тех задачах, где новое значение функции вычисляется из одного предыдущего (которое и перезаписывается).
Если бы формула была сложнее, например, как в числах Фибоначчи, где нужно хранить сразу несколько предыдущих значений, то алгоритм пришлось бы пересмотреть.
В этом кроется частая ошибка — пытаться хранить все значения функции в списке или словаре. В большинстве задач это не только не нужно, но и вредно.
Если F(n) зависит только от одного следующего или предыдущего значения, достаточно одной переменной. Она всегда содержит актуальное значение функции. Когда нам нужно сохранить конкретный результат, например F(81) или F(2024), мы просто копируем текущее значение в отдельную переменную!
Давайте выразим все наши размышления в виде кода. Сначала записываем стартовое значение (в нашем примере это 1):
Далее идёт цикл от первого неизвестного значения (2) до искомого значения (у нас это 10):
Внутри цикла записываем формулу для вычисления F(n):
Останется лишь вывести последнее значение переменной F:
Здесь важно понимать, что переменная F всегда хранит последнее вычисленное значение функции, а цикл идет строго в сторону увеличения n.
Но также можно встретить обратную ситуацию, когда F(n) выражается через F(n + 1) или F(n + 2). Например:
F(n)=n, при n ≥ 2025;
F(n)= n · 2 + F(n+2), если n < 2025
Здесь функция не уходит «назад», а наоборот, прыгает вперед. Это сразу означает, что считать нужно с конца.
Сначала мы понимаем, где вычисление гарантированно останавливается. В данном случае это любые n, не меньшие 2025. Значит, реальные вычисления начнутся с ближайшего подходящего значения, например 2026 или 2025, в зависимости от чётности.
Дальше мы идем назад, уменьшая n на нужный шаг. Если формула использует F(n + 2), значит шаг цикла тоже равен 2. На каждом шаге мы уже знаем значение F для большего аргумента и можем посчитать текущее.
Фактически мы как бы разматываем рекурсию в обратную сторону.
А в коде, чтобы «спуститься» до конкретного значения, например, до F(81) мы изначально приравняем искомое значение к максимальному, то есть 2025:
Далее в цикле будем перебирать все нечётные значения до 2023 до 80 с отрицательным шагом -2:
И на каждой итерации будем пересчитывать значение в переменной F81 по формуле из условия:
Давайте теперь сделаем краткий вывод и напишем шаблон под каждую ситуацию.
Ситуация 1. Движение вверх
Когда вы видите, что в формуле стоит знак минус между n и числом: F(n — 1), F(n — 2) и т.п., то нужно вычислять значения снизу вверх.
Обычно в таких задачах есть стартовое значение вида F(1) = … или F(2) = …. С него и начинаем.
Алгоритм всегда один и тот же: мы заводим переменную F, кладём в неё стартовое значение и идём циклом вперёд, каждый раз пересчитывая F по формуле.
Шаблон кода будет такой:
Ситуация 2. Движение вниз.
Когда вы видите, что в формуле стоит знак плюс между n и числом: F(n + 1), F(n + 2) и т.п., то нужно вычислять значения сверху вниз.
В таких задачах всегда есть граница, начиная с которой функция задана явно, например: F(n) = n при n ≥ 2025.
Именно от этой границы и начинается вычисление. Дальше мы идём назад, уменьшая n с тем же шагом, который используется в формуле. Если в формуле F(n + 2), шаг цикла тоже равен 2, если F(n+3) — шаг равен 3. Обязательно учитывать чётность: чётные и нечётные значения считаются отдельно.
Шаблон здесь следующий:
Теперь давайте проверим это всё на практике. Формулировка будет такая:
«Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n)=2 · n · F(n-1), если n>1
Чему равно значение выражения (F(2024)/16-F(2023))/F(2022)?»
Видим в формуле n-1, знак минус, значит идти будем снизу вверх. Выпишем начальное значение F (единицу) и создадим переменные для искомых величин: F(2022), F(2023), F(2024):
Запускаем цикл от 2 до 2025 (с шагом 1):
Далее переписываем выражение из условия:
И создаём «точки сохранения» для каждого искомого значения:
Всё, значения сохранены, теперь подсчитываем результат выражения:
И выводим на экран значение переменной result:
Запускаем программу и получаем ответ на это задание — число 1019592.
Решение с мемоизацией
Напоследок разберём самый простой в понимании, но не менее эффективный метод решения. Здесь мы будем описывать всю ту же рекурсивную функцию, но для сохранения результатов вычисления и спасения от превышения глубины рекурсии будем использовать декоратор @lru_cache.
На рассмотрении у нас такое задание:
«Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(n)=1 при n ≤ 5;
F(n)= n + F(n-2), если n > 5
Чему равно значение выражения F(2126) — F(2122)?»
Начнём решение с импорта декоратора lru_cache из модуля functools:
Далее объявим функцию f() и задекорируем её:
А теперь буквально по фразам реализуем соотношения из условия в коде. Фразу «при n ≤ 5» можно воспринимать как «если n ≤ 5», тут само просится условие с оператором if:
Далее в тексте задания говорится, что при таких значения n, функция F возвращает единицу, так и запишем:
Всю остальную часть из условия поместим в блок else:
Функция готова, но теперь надо «прогнать» её по всем числам до 2126, чтобы «наполнить» кеш значениями от 5 до 2126. Это нам поможет избежать рекурсии при вычислении f(2126) и f(2122) — Python просто возьмёт числа из кеша, без вычисления.
Делать мы это будем, конечно же, с помощью цикла for:
Осталось лишь вывести на экран разность значений f(2126) и f(2122):
В результате работы программы получаем число 4250, которое и будет ответом на данное задание.
С этим методом решения мы еще больше попрактикуемся в следующей статье, которая посвящена методам решения 16 заданий второго типа.