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

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

Тип 2. Две связанные функции

С несколькими методами решения 16 заданий первого типа мы уже познакомились еще в прошлой статье. Чаще всего применяются такие методы:

  1. Ручное решение
  2. Итеративный подход
  3. Оптимизация рекурсии

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

Не нужно автоматически считать рекурсивными обе функции. Сначала нарисуйте зависимости стрелками: F → G означает, что F использует G; G → G означает настоящую рекурсивную цепочку внутри G.

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

Ручное решение возможно, но при больших аргументах код с @lru_cache обычно короче и надёжнее. Именно этим способом и будем решать 16 задания второго типа.

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

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

После чего, можем начать писать код вот по такому алгоритму:

  1. Записываем обе функции точно по условию и ставим @lru_cache(maxsize=None) перед рекурсивной функцией.
  2. Определяем направление: при G(n − k) значения готовим по возрастанию, а при G(n + k) — по убыванию.
  3. До итогового вызова «прогоняем» нужный диапазон, чтобы каждый новый вызов опирался на уже готовое значение.

Начнём разбор алгоритма решения с такой формулировки:

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

F(n)= 2 × (G(n-3)+8);
G(n)=2 × n, если n < 10
G(n)=G(n-2) + 1, если n ≥ 10

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

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

Функция F сама себя не вызывает: она лишь один раз обращается к G. Рекурсия находится в G(n) = G(n − 2) + 1, поэтому кешировать будем именно G.

При вызове F(15548) понадобится G(15545). Эта функция запросит G(15543), затем G(15541) и продолжит уменьшать аргумент на 2, пока не попадёт в область n < 10.

Если строить эту цепочку сразу, глубина будет огромной. Предварительный прогон создаёт результаты снизу вверх: когда вычисляется очередное G(k), значение G(k − 2) уже хранится в кеше.

Базовый случай G задан для всех n < 10: там ответ сразу равен 2 · n.

  1. При n ≥ 10 аргумент уменьшается на 2. Значит, значения нужно готовить от меньших аргументов к большим.
  2. Декоратор нужен G, а F останется обычной функцией.

Что же, приступим к решению, для начала импортируем lru_cache из модуля functools:

from functools import lru_cache

Далее нам следует определить функцию f:

from functools import lru_cache


def f(n):
    return 2 * (g(n - 3) + 8)

Теперь переходим к функции g, её значения мы и будем сохранять в кеше, значит, используем здесь декоратор @lru_cache:

from functools import lru_cache


def f(n):
    return 2 * (g(n - 3) + 8)


@lru_cache(maxsize=None)
def g(n):
    if n < 10:
        return 2 * n
    else:
        return g(n - 2) + 1

Обе функции точно по условию записали — шаг 1 нашего алгоритма выполнен. Теперь нужно определить направление по функции G.

Будем вызывать f(n) по возрастанию. При каждом таком вызове f обратится к g(n − 3), а нужное ему g(n − 5) уже окажется в кеше. Следовательно, значения готовим по возрастанию. Перебираем f(n) от 10 до 15548 включительно, поэтому правая граница range равна 15549:

from functools import lru_cache


def f(n):
    return 2 * (g(n - 3) + 8)


@lru_cache(maxsize=None)
def g(n):
    if n < 10:
        return 2 * n
    else:
        return g(n - 2) + 1


for n in range(10, 15549):
    f(n)

Тем самым мы «прогнали» нужный диапазон, чтобы каждый новый вызов опирался на уже готовое значение. Осталось лишь вывести значение функции f с аргументом 15548:

from functools import lru_cache


def f(n):
    return 2 * (g(n - 3) + 8)


@lru_cache(maxsize=None)
def g(n):
    if n < 10:
        return 2 * n
    else:
        return g(n - 2) + 1


for n in range(10, 15549):
    f(n)

print(f(15548))

Запускаем программу и получаем число 15588, которое и запишем в ответ.

Пример 1

Рассмотрим решение еще одного похожего задания:

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

F(n)= G(n-1) + G(n-3);
G(n)=3 × n, если n ≤ 9
G(n)=G(n-4) + 2, если n > 9

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

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

Здесь G(n) зависит от G(n − 4). Значит, снова готовим значения по возрастанию аргумента.

Шаг 4 (в n − 4)  создаёт уже четыре независимые цепочки остатков. Цикл по всем n с шагом 1 подготавливает их одновременно и избавляет нас от ручного выбора нужного остатка.

Вызываем f(n) от 9 до 42999. Так кеш G постепенно заполнится в нужном порядке.

Импортируем функцию кеширования и пишем собственную функцию для F:

from functools import lru_cache


def f(n):
    return g(n-1) + g(n-3)

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

from functools import lru_cache


def f(n):
    return g(n-1) + g(n-3)


@lru_cache(maxsize=None)
def g(n):
    if n <= 9:
        return 3 * n
    else:
        return g(n - 4) + 2

В цикле «прогоняем» функцию f от 9 до 43000 (не включительно):

from functools import lru_cache


def f(n):
    return g(n-1) + g(n-3)


@lru_cache(maxsize=None)
def g(n):
    if n <= 9:
        return 3 * n
    else:
        return g(n - 4) + 2


for n in range(9, 43000):
    f(n)

Выводим результат на экран:

from functools import lru_cache


def f(n):
    return g(n-1) + g(n-3)


@lru_cache(maxsize=None)
def g(n):
    if n <= 9:
        return 3 * n
    else:
        return g(n - 4) + 2


for n in range(9, 43000):
    f(n)

print(f(42999))

Запустив программу, через мгновение обнаружим на экране число 43032, которое и будет ответом на это задание.

Пример 2

Напоследок рассмотрим задание с противоположным движением рекурсии:

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

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

В этом примере рекурсивны обе функции. Однако F уменьшает аргумент на 4 и от 673 доходит до базового случая менее чем за 200 шагов. Это безопасная глубина, поэтому кеш нужен прежде всего для G.

Здесь граф зависимостей выглядит сложнее: F → F, затем в базовой ветке F → G, а внутри G есть стрелка G → G. У двух рекурсий разные направления и разная глубина.

Цепочка F короткая и движется вниз с шагом 4. Цепочка G очень длинная и движется вверх с шагом 9. Поэтому решение можно оставить рекурсивным для F, но G обязательно подготовить заранее.

В G(n) = G(n + 9) − 4 аргумент, наоборот, увеличивается. Чтобы не строить цепочку из десятков тысяч вызовов, заполняем кеш от больших n к меньшим.

Важно найти самый маленький аргумент G, который понадобится. F(673) идёт так: 673, 669, …, 21, 17. При n = 17 она обращается к G(10). Значит, кеш G нужно заполнить как минимум до 10, а не до 600.

Начинаем с 248045: для него действует базовый случай. Затем спускаемся до 10: при каждом вызове g(n) значение g(n + 9) уже известно или сразу попадает в базовый случай.

С теорией закончили, давайте приступать к решению. Как обычно, импортируем lru_cache:

from functools import lru_cache

Записываем первую функцию без декоратора:

from functools import lru_cache


def f(n):
    if n < 19:
        return 6 * (g(n - 7) - 36)
    else:
        return f(n - 4) + 3580

И вторую функцию с @lru_cache:

from functools import lru_cache


def f(n):
    if n < 19:
        return 6 * (g(n - 7) - 36)
    else:
        return f(n - 4) + 3580


@lru_cache(maxsize=None)
def g(n):
    if n < 248045:
        return g(n + 9) - 4
    else:
        return n / 20 + 28

В цикле идём от 248045 до 10 включительно. Шаг берём −1, а не −9: так мы заполним все классы остатков по модулю 9:

Начальное значение 248045 само попадает в базовый случай. Для 248044 потребуется G(248053), которое тоже базовое, а для более низких аргументов нужные значения постепенно начнут браться из кеша.

Спуск с шагом −1 кажется избыточным, зато гарантированно готовит все девять классов остатков. На экзамене надёжный полный прогон обычно лучше хрупкой оптимизации на несколько строк.

from functools import lru_cache


def f(n):
    if n < 19:
        return 6 * (g(n - 7) - 36)
    else:
        return f(n - 4) + 3580


@lru_cache(maxsize=None)
def g(n):
    if n < 248045:
        return g(n + 9) - 4
    else:
        return n / 20 + 28


for n in range(248045, 9, -1):
    g(n)

И выводим значение вызова функции f с аргументом 673:

from functools import lru_cache


def f(n):
    if n < 19:
        return 6 * (g(n - 7) - 36)
    else:
        return f(n - 4) + 3580


@lru_cache(maxsize=None)
def g(n):
    if n < 248045:
        return g(n + 9) - 4
    else:
        return n / 20 + 28


for n in range(248045, 9, -1):
    g(n)

print(f(673))

Программа выведет 47.0. В ответ записываем целое число 47. Десятичная точка появилась из-за оператора / в формуле G(n) = n / 20 + 28.

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

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

Следите за направлением предварительного прогона. Для зависимости G(n − k) идём вверх, а для G(n + k) — вниз. При шаге k > 1 учитывайте отдельные классы остатков или безопасно перебирайте все аргументы с шагом 1.

Итоги

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

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

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

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