Тип 2
С несколькими методами решения 16 заданий первого типа мы уже познакомились еще в прошлой статье. Чаще всего применяются такие методы:
- Ручное решение
- Итеративный подход
- Оптимизация рекурсии
Задания второго типа мы будем решать именно последним методом — с использованием декоратора @lru_cache. Вспомним, чем отличается второй тип: здесь нам предстоит работать не с одной, а сразу с двумя функциями.
Вы, конечно, можете решать такие задания вручную, но это займёт гораздо больше времени, чем написание программного кода с кешированием.
Освежим в памяти алгоритм решения заданий 16 через @lru_cache:
- Выписываем функцию из условия задания: сначала оформляем базовый случай (когда функция возвращает известное число), затем рекурсивный (когда она вызывает саму себя)
- «Прогоняем» функцию в цикле по всем значениям — от первого неизвестного до максимального из аргументов функции в выражении из условия
Для заданий второго типа от нас потребуется всего лишь добавить ещё одну функцию, но уже без декоратора.
Алгоритм решения
Начнём разбор алгоритма решения с такой формулировки:
«Алгоритм вычисления значения функций 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)?»
Видим, что теперь появилась функция G(n), от которой зависит привычная нам функция F(n). Давайте внимательно посмотрим, для какой функции есть стартовая точка и граничные условия.
Верно, для функции G(n):
- Стартовая точка у нас не явная, как в некоторых других заданиях, но значения функции с аргументами меньше 10 можно получить без проблем из этой записи: G(n) = 2 · n, если n < 10
- Число 10 как раз и будет границей. То есть при аргументах n ≥ 10 функция G(n) будет иметь рекурсивный вызов G(n-2)
О чём это говорит? Декорировать нам придётся именно функцию G, тогда как для F можно обойтись обычным определением функции без какого-либо кеширования.
Приступим к решению, для начала импортируем lru_cache из модуля functools:
Далее нам следует определить функцию f():
Теперь переходим к функции g(), её значения мы и будем сохранять в кеше, значит, используем здесь декоратор @lru_cache:
Следом нужно в цикле «прогнать» все значения рекурсивной функции. Но какой?
Здесь следует поместить в цикл именно функцию f(), потому что сама f() не рекурсивная и при каждом вызове гарантированно обращается к g() с аргументами меньше текущего n. Благодаря этому кеш g() заполняется постепенно и в безопасном порядке.
Если бы вы напрямую вызывали g() с большими n, первая же попытка ушла бы глубоко вниз по рекурсии. А «прогон» f() по возрастанию n аккуратно вычисляет все нужные значения g(), не создавая большой глубины стека вызовов.
Передавать в функцию f() будем значения от 10 до 15549 (не включительно):
В конце потребуется лишь вывести значение функции 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 и числом). Подробнее «движение» рекурсии мы рассматривали в главе про итеративный подход в прошлой статье.
Что это значит? Снова в цикле будем вызывать именно функцию f() с аргументами от наименьшего известного числа (9) до требуемого по условию аргумента f() — 42999 включительно.
Импортируем функцию кеширования и пишем собственную функцию для F:
Добавляем код второй функции, значения которой должны кешироваться:
В цикле «прогоняем» функцию f() от 9 до 43000 (не включительно):
Выводим результат на экран:
Запустив программу, через мгновение обнаружим на экране число 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 тоже имеет рекурсию. Но это не значит, что нам придётся её декорировать! Декоратор @lru_cache всё так же будем применять ко второй функции.
Что действительно стоит отметить, так это знак плюс в выражении для второй функции: G(n) = G(n+9) – 4. Это означает, что рекурсия движется вниз (аргументы вычисляются сверху вниз). Как это скажется на решении?
В данном задании нам придётся «перевернуть» цикл, то есть перебирать значения от большего к меньшему. И в самом цикле у нас будет вызываться функция g(), а не f(), как в прошлых примерах. Причина в том, что рекурсия сосредоточена в ней и идёт в сторону увеличения аргумента, поэтому прямой вызов g() с малым n сразу приводит к глубокой рекурсии и ошибке.
Предварительный вызов g() для всех n в обратном порядке заставляет сначала посчитать все базовые случаи, после чего остальные значения просто берутся из кеша, и f() уже работает быстро, не провоцируя опасную рекурсию.
С теорией закончили, давайте приступать к решению. Как обычно, импортируем lru_cache:
Записываем первую функцию без декоратора:
И вторую функцию с @lru_cache:
В цикле прогоняем значения от 248046 до 600 в обратном порядке:
И выводим значение вызова функции f() с аргументом 673:
Запустим программу и увидим на экране число 47. Это и будет ответом на данное задание.
Больше заданий данного типа с подробным решением вы можете найти в нашем тренажёре.