ЕГЭ, ОГЭ, программирование и робототехника в Калининграде

Алгоритм решения задания 16. Часть 1

О задании

В прошлых статьях мы разобрались, как работает рекурсия, почему возникает RecursionError и как мемоизация убирает повторные вычисления.

Теперь перейдём к самому заданию 16. В нём нужно вычислить значение выражения с одной или двумя функциями, заданными рекурсивно.

Экзаменационная формула выглядит как программа, записанная математическими обозначениями. Каждая строка задаёт ветку if, а обращение F к самой себе превращается в обычный вызов функции.

Но писать рекурсивный код сразу необязательно. Иногда разность соседних значений сокращается вручную, а иногда безопаснее развернуть зависимость циклом.

Будем разделять задания по структуре:

  1. первый тип — в условии одна функция F;
  2. второй тип — в условии две связанные функции F и G.

В этой статье разберём первый тип тремя способами: вручную, циклом и рекурсией с @lru_cache. Так вы сможете выбрать на экзамене самый удобный вариант.

Алгоритм решения

Ручное решение

Многие задания с экзаменов прошлых лет легко решаются ручным методом. Суть его заключается в буквальном вычислении значений функций и выявлении зависимостей между этими значениями.

Рассмотрим этот способ на примере задания с такой формулировкой:

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

F(n)=n при n ≥ 2025;
F(n)= n × 2 + F(n+2), если n < 2025

Чему равно значение выражения F(82) - F(81)?

Открыть задание

Давайте анализировать имеющиеся соотношения. Сразу можно обратить внимание на два момента:

  1. Если n меньше 2025, функция вызывает себя с аргументом n + 2
  2. Значит, F(82) будет обращаться к F(84), F(86), F(88) и так далее по чётным числам. А F(81) будет обращаться к F(83), F(85), F(87) и так далее по нечётным.

Шаг +2 делит все вызовы на две независимые цепочки по остаткам от деления на 2. Чётная цепочка никогда не попадёт в нечётную и наоборот. Цепочка F(82) идёт по чётным числам и останавливается на F(2026). Цепочка F(81) идёт по нечётным и останавливается на F(2025). В обоих случаях аргумент уже не меньше 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 — шаг прогрессии

Эту формулу легко восстановить самостоятельно. Разность L − A показывает путь от первого числа до последнего. Деление на шаг d даёт количество переходов, а элементов всегда на один больше, чем переходов.

В последовательности 82, 84, …, 2024 всего (2024 − 82) / 2 + 1 = 972 члена. Поэтому F(82) = 2 · (82 + 84 + … + 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.

Итеративный подход

Да, ручное решение порой бывает сложным. Не всегда можно увидеть закономерности в математических формулах, чтобы с их помощью упростить вычисления. В таком случае, можно перейти к циклу. Мы посчитаем те же значения в безопасном порядке, но без глубокого стека вызовов.

Цикл в таких задачах не является другим математическим методом. Он выполняет те же зависимости, только мы сами выбираем порядок и не создаём отдельный фрейм для каждого значения.

Главный вопрос здесь: в каком порядке нужно получать значения, чтобы к моменту вычисления F(n) все нужные значения уже были известны.

Главная идея такого подхода в том, что если значение функции зависит от соседних значений, то:

  1. Существует порядок, в котором их можно посчитать
  2. Каждое новое значение можно получить из уже известного

Итеративный подход особенно удобен в двух ситуациях:

  1. если F(n) зависит от F(n − 1), F(n − 2) и так далее, считаем от меньших n к большим;
  2. если F(n) зависит от F(n + 1), F(n + 2) и так далее, начинаем с базовой границы и идём к меньшим n.
  1. В обоих случаях первой ищем строку, где функция задана без вызова самой себя. Это стартовое значение для цикла.

Как вы можете заметить, все эти три пункта подходят под большинство 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(n) зависит только от одного следующего или предыдущего значения, достаточно одной переменной. Она всегда содержит актуальное значение функции. Когда нам нужно сохранить конкретный результат, например F(81) или F(2024), мы просто копируем текущее значение в отдельную переменную!

Давайте выразим все наши размышления в виде кода. Сначала записываем стартовое значение (в нашем примере это 1):

# стартовое значение
F = 1  # это F(1)

Далее идёт цикл от первого неизвестного значения (2) до искомого значения (у нас это 10):

# стартовое значение
F = 1  # это F(1)
# До F(10)
for n in range(2, 11):

Внутри цикла записываем формулу для вычисления F(n):

# стартовое значение
F = 1  # это F(1)
# До F(10)
for n in range(2, 11):     
    F = 2 * n * F

Останется лишь вывести последнее значение переменной F:

# стартовое значение
F = 1  # это F(1)
# До F(10)
for n in range(2, 11):     
    F = 2 * n * F
print(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

Здесь функция не уходит «назад», а наоборот, прыгает вперед. Это сразу означает, что считать нужно с конца.

Сначала важно учесть чётность. Для F(81) цепочка заканчивается на F(2025), а для F(82) — на F(2026).

Дальше мы идем назад, уменьшая n на нужный шаг. Если формула использует F(n + 2), значит шаг цикла тоже равен 2. На каждом шаге мы уже знаем значение F для большего аргумента и можем посчитать текущее.

Фактически мы как бы разматываем рекурсию в обратную сторону.

А в коде, чтобы «спуститься» до конкретного значения, например, до F(81) мы изначально приравняем искомое значение к максимальному, то есть 2025:

F81 = 2025

Далее перебираем нечётные n от 2023 до 81 включительно. В range правая граница не включается, поэтому пишем 80:

F81 = 2025

for n in range(2023, 80, -2):

И на каждой итерации будем пересчитывать значение в переменной F81 по формуле из условия:

F81 = 2025

for n in range(2023, 80, -2):
    F81 = 2 * n + F81

Давайте теперь сделаем краткий вывод и напишем шаблон под каждую ситуацию.

Ситуация 1. Движение вверх

Когда вы видите, что в формуле стоит знак минус между n и числом: F(n — 1), F(n — 2) и т.п., то нужно вычислять значения снизу вверх.

Обычно в таких задачах есть стартовое значение вида F(1) = … или F(2) = …. С него и начинаем.

Алгоритм всегда один и тот же: мы заводим переменную F, кладём в неё стартовое значение и идём циклом вперёд, каждый раз пересчитывая F по формуле.

Шаблон кода будет такой:

F = стартовое_значение   # Например, F(1)
for n in range(первое_неизвестное, нужное_n + 1):
    F = формула_из_условия
    if n == нужное_n:
        Fn = F

Ситуация 2. Движение вниз.

Если шаг равен 2, 3 или 4, следите не только за направлением, но и за классом остатков. При шаге 3 значения 10, 13, 16 образуют одну цепочку, а 11, 14, 17 — уже другую.

Стартовое значение для каждой цепочки может оказаться своим. Поэтому сначала проследите путь именно от нужного аргумента до базовой области, а затем переносите его в range.

Когда вы видите, что в формуле стоит знак плюс между n и числом: F(n + 1), F(n + 2) и т.п., то нужно вычислять значения сверху вниз.

В таких задачах всегда есть граница, начиная с которой функция задана явно, например: F(n) = n при n ≥ 2025.

Именно от этой границы и начинается вычисление. Дальше мы идём назад, уменьшая n с тем же шагом, который используется в формуле. Если в формуле F(n + 2), шаг цикла тоже равен 2, если F(n+3) — шаг равен 3. Обязательно учитывать чётность: чётные и нечётные значения считаются отдельно.

Шаблон здесь следующий:

F = граничное_значение   # Например, F(2025)
for n in range(начало, конец, -шаг):
    F = формула_из_условия
    if n == нужное_n:
        Fn = F

Теперь давайте проверим это всё на практике. Рассмотрим еще одно 16 задание с такой формулировкой:

Алгоритм вычисления значения функции 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):

F = 1
f2022 = 0
f2023 = 0
f2024 = 0

Запускаем цикл от 2 до 2025 (с шагом 1):

F = 1
f2022 = 0
f2023 = 0
f2024 = 0

for n in range(2, 2025):

Далее переписываем выражение из условия:

F = 1
f2022 = 0
f2023 = 0
f2024 = 0

for n in range(2, 2025):
    F = 2 * n * F

И создаём «точки сохранения» для каждого искомого значения:

F = 1
f2022 = 0
f2023 = 0
f2024 = 0

for n in range(2, 2025):
    F = 2 * n * F
    if n == 2022:
        f2022 = F
    elif n == 2023:
        f2023 = F
    elif n == 2024:
        f2024 = F

Всё, значения сохранены, теперь подсчитываем результат выражения:

F = 1
f2022 = 0
f2023 = 0
f2024 = 0

for n in range(2, 2025):
    F = 2 * n * F
    if n == 2022:
        f2022 = F
    elif n == 2023:
        f2023 = F
    elif n == 2024:
        f2024 = F

result = (f2024 // 16 - f2023) // f2022

И выводим на экран значение переменной result:

F = 1
f2022 = 0
f2023 = 0
f2024 = 0

for n in range(2, 2025):
    F = 2 * n * F
    if n == 2022:
        f2022 = F
    elif n == 2023:
        f2023 = F
    elif n == 2024:
        f2024 = F

result = (f2024 // 16 - f2023) // f2022
print(result)

Запускаем программу и получаем ответ на это задание — число 1019592.

Решение с мемоизацией

Ещё один вариант — записать функцию по условию и добавить @lru_cache. Кеш уберёт повторные вычисления, а предварительный «прогон» по возрастанию не даст одной цепочке вызовов стать слишком длинной.

Предварительный прогон работает как лестница. Вызов f(6) использует только базовые значения, f(7) тоже. Когда очередь дойдёт до f(2126), почти вся длинная цепочка уже лежит в кеше.

Если вызвать f(2126) первым, декоратор не сможет взять ответы из будущего: кеш ещё пуст. Он уберёт повторения, но построит один путь глубиной больше тысячи и может получить RecursionError.

На рассмотрении у нас такое задание:

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

F(n)=1 при n ≤ 5;
F(n)= n + F(n-2), если n > 5

Чему равно значение выражения F(2126) - F(2122)?

Открыть задание

Начнём решение с импорта декоратора lru_cache из модуля functools:

from functools import lru_cache

Далее объявим функцию f и задекорируем её:

from functools import lru_cache


@lru_cache(maxsize=None)
def f(n):

А теперь буквально по фразам реализуем соотношения из условия в коде. Фразу «при n ≤ 5» можно воспринимать как «если n ≤ 5», тут само просится условие с оператором if:

from functools import lru_cache


@lru_cache(maxsize=None)
def f(n):
    if n <= 5:

Далее в тексте задания сказано, что при таких значениях n функция F возвращает единицу. Так и запишем:

from functools import lru_cache


@lru_cache(maxsize=None)
def f(n):
    if n <= 5:
        return 1

Всю остальную часть из условия поместим в блок else:

from functools import lru_cache


@lru_cache(maxsize=None)
def f(n):
    if n <= 5:
        return 1
    return n + f(n - 2)

Если сразу вызвать f(2126), получится цепочка более чем из тысячи вызовов. @lru_cache сам по себе её не укоротит. Поэтому заранее вызовем f(n) для всех n по возрастанию.

Делать мы это будем, конечно же, с помощью цикла for:

from functools import lru_cache


@lru_cache(maxsize=None)
def f(n):
    if n <= 5:
        return 1
    return n + f(n - 2)


for n in range(5, 2127):
    f(n)

Осталось лишь вывести на экран разность значений f(2126) и f(2122):

from functools import lru_cache


@lru_cache(maxsize=None)
def f(n):
    if n <= 5:
        return 1
    return n + f(n - 2)


for n in range(5, 2127):
    f(n)

print(f(2126) - f(2122))

В результате работы программы получаем число 4250, которое и будет ответом на данное задание.

Проверим результат без полного вычисления огромных значений. По формуле F(2126) = 2126 + F(2124), а F(2124) = 2124 + F(2122). Поэтому разность равна 2126 + 2124 = 4250.

Такая короткая ручная проверка полезна даже после запуска программы: она подтверждает, что мы правильно перенесли шаг −2 и порядок вычитания.

Типичные ошибки

Не начинайте вычисления, пока не нашли базовый случай и направление зависимости. В ручном решении следите за количеством переходов, а в range — за невключённой правой границей.

При шагах больше единицы учитывайте чётность или остаток. В рекурсивном решении помните: lru_cache убирает повторы, но длинную первую цепочку нужно разбить предварительным прогоном.

Итоги

В первом типе задания 16 мы освоили три взгляда на одну рекуррентную формулу. Ручной метод помогает увидеть сокращение, цикл явно задаёт безопасный порядок, а рекурсия с кешем почти буквально повторяет условие. В следующей статье перенесём эти идеи на две связанные функции.

Разберём эту тему на бесплатном пробном занятии

Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.

Записаться на пробное занятие