Алгоритм вычисления значения функций 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)?
С несколькими методами решения 16 заданий первого типа мы уже познакомились еще в прошлой статье. Чаще всего применяются такие методы:
Во втором типе одна функция обычно обращается к другой. Нам нужно определить, какая из них действительно рекурсивна, и заполнить её кеш в безопасном порядке.
Не нужно автоматически считать рекурсивными обе функции. Сначала нарисуйте зависимости стрелками: F → G означает, что F использует G; G → G означает настоящую рекурсивную цепочку внутри G.
Такой маленький граф сразу показывает, где возникает глубина, какую функцию кешировать и в каком порядке готовить значения.
Ручное решение возможно, но при больших аргументах код с @lru_cache обычно короче и надёжнее. Именно этим способом и будем решать 16 задания второго типа.
Перед составления программы полезно ответить на четыре вопроса: где базовая область, как меняется аргумент, какой минимальный или максимальный аргумент понадобится и какие остатки по модулю шага образуют отдельные цепочки.
После чего, можем начать писать код вот по такому алгоритму:
@lru_cache(maxsize=None) перед рекурсивной функцией.Начнём разбор алгоритма решения с такой формулировки:
Алгоритм вычисления значения функций 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.
Что же, приступим к решению, для начала импортируем 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, которое и запишем в ответ.
Рассмотрим решение еще одного похожего задания:
Алгоритм вычисления значения функций 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, которое и будет ответом на это задание.
Напоследок рассмотрим задание с противоположным движением рекурсии:
Алгоритм вычисления значения функции 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.
В задачах с двумя функциями сначала строим карту зависимостей, находим базовые области и оцениваем глубину каждой цепочки. После этого становится понятно, какую функцию кешировать и в каком направлении заполнять кеш.