Автор статьи: Андрей Рогов
Введение
Эта статья — четвёртая в серии статей по теории игр. До этого рассмотрели аналитическое решение, решение в электронных таблицах и динамическое программное решение. Рекурсивный подход позволяет сократить необходимый объём кода, но при этом он более требователен к ресурсам компьютера.
Основные компоненты рекурсии:
- базовый случай (условие остановки)
«Точка выхода» из рекурсии — простейшая ситуация, когда функция не вызывает себя, а сразу возвращает результат.
Без этого рекурсия будет бесконечной. - рекурсивный случай\
Здесь функция вызывает себя с изменёнными параметрами, приближая задачу к базовому случаю
Решая задачу аналитически, мы определяем для каждой позиции, какая она:
- конечная позиция — игра заканчивается, потому что достигнуто окончательное число камней
- В1 — выигрышная позиция за один ход: существует хотя бы один ход в конечную позицию
- П1 — проигрышная позиция за один ход: все ходы ведут в В1
- В2 — выигрышная позиция за два хода: существует хотя бы один ход в П1
- П2 — проигрышная позиция за один (не гарантированно) или два хода: все ходы ведут в В1 или В2
Базовыми случаями здесь будут конечные позиции, все остальные — рекурсивными.
Задача 1. Одна куча камней, два разных хода
Воспользуемся теми же обозначениями, что и в статье о динамическом методе решения:
Конечные позиции все начиная от 301 и больше.
def g(s):
# Базовый случай
if s >= 301:
return 5
Для описания рекурсивных случаев добавим функцию, вычисляющую возможные ходы из текущей позиции.
Если существует ход из позиции S, при котором функция будет равна 5, позиция окажется выигрышной за 1 ход.
Воспользуемся сразу сокращением кода — функцией any().
def m(s):
return s + 3, s * 5
def g(s):
# Базовый случай
if s >= 301:
return 5
# Рекурсивные случаи
# Если есть хотя бы один ход в конечную позицию
if any(g(i) == 5 for i in move(s)):
return 1
Аналогично динамическому решению каждая последующая позиция вычисляется в соответствии с её определением.
def m(s):
return s + 3, s * 5
def g(s):
# Базовый случай
if s >= 301:
return 5
# Рекурсивные случаи
# Если есть хотя бы один ход в конечную позицию
if any(g(i) == 5 for i in m(s)):
return 1 # победа первым ходом
# Если все ходы ведут в В1
if all(g(i) == 1 for i in m(s)):
return -1 # поражение первым ходом
# Если есть хотя бы один ход в проигрышную позицию
if any(g(i) == -1 for i in m(s)):
return 2 # победа вторым ходом
# Если все ходы ведут в В1 или В2
if all(g(i) > 0 for i in m(s)):
return -2 # поражение первым ходом
return 0 # неопределённый случай
Осталось перебрать все возможные начальные значения S и вывести подходящие на экран.
for s in range(1, 301):
if g(s) == -1:
print(s)
К сожалению, такой код не сможет вывести ответ, поскольку требуется слишком много вычислений. Выходом из ситуации служит мемоизация.
Мемоизация — техника оптимизации, при которой вычисленные результаты сохраняются для повторного использования. Её можно выполнить вручную, сохраняя все значения в словарь.
def m(s):
return s + 3, s * 5
def g(s):
# Если вариант уже был вычислен
if s in d:
return d[s]
# Базовый случай
if s >= 301:
d[s] = 5
return 5
# Рекурсивные случаи
# Если есть хотя бы один ход в конечную позицию
if any(g(i) == 5 for i in m(s)):
d[s] = 1
return 1 # победа первым ходом
# Если все ходы ведут в В1
if all(g(i) == 1 for i in m(s)):
d[s] = -1
return -1 # поражение первым ходом
# Если есть хотя бы один ход в проигрышную позицию
if any(g(i) == -1 for i in m(s)):
d[s] = 2
return 2 # победа вторым ходом
# Если все ходы ведут в В1 или В2
if all(g(i) > 0 for i in m(s)):
d[s] = -2
return -2 # поражение первым ходом
d[s] = 0
return 0 # неопределённый случай
d = dict()
for s in range(1, 301):
if g(s) == -1:
print(s)
Однако в язык Python встроен декоратор lru_cache, позволяющий автоматически запоминать значения. Название LRU означает least recently used — «наименее недавно использованный».
Декоратор использует словарь: результат выполнения функции кешируется под ключом, соответствующим вызову функции и предоставленным аргументам. Если кеш заполнен, удаляется элемент, который использовался наиболее давно. У декоратора lru_cache есть два параметра:
- maxsize (по умолчанию 128) определяет максимальный размер кеша, то есть результаты скольких вызовов функций будут сохранены. Если установить maxsize=None, то все будут сохраняться до тех пор, пока не закончится память
- typed (по умолчанию False) — если установлено значение True, то результаты вызова функции с аргументами разных типов (например, f(3) и f(3.0)) будут сохраняться как отдельные записи. Если установлено значение False, то результаты вызова функции с аргументами разных типов будут сохранены в одну запись
from functools import lru_cache
def m(s):
return s + 3, s * 5
@lru_cache(None)
def g(s):
# Базовый случай
if s >= 301:
return 5
# Рекурсивные случаи
# Если есть хотя бы один ход в конечную позицию
if any(g(i) == 5 for i in m(s)):
return 1 # победа первым ходом
# Если все ходы ведут в В1
if all(g(i) == 1 for i in m(s)):
return -1 # поражение первым ходом
# Если есть хотя бы один ход в проигрышную позицию
if any(g(i) == -1 for i in m(s)):
return 2 # победа вторым ходом
# Если все ходы ведут в В1 или В2
if all(g(i) > 0 for i in m(s)):
return -2 # поражение первым ходом
return 0 # неопределённый случай
for s in range(1, 301):
if g(s) == -1:
print(s)
Вывод программы:
Таким образом, рекурсивное решение сохраняет все преимущества рассмотренных решений:
- мнемонически совпадает с аналитическим решением
- не требует ручных вычислений
- позволяет писать код копированием фрагментов
- адаптируется ко всем стандартным для ЕГЭ формулировкам
К этим преимуществам добавляется компактность кода.
Задача 2. Убирание камней
Сложность представляет только определение верхней границы перебора начального количества камней. При определении позиций дважды используется «сильный» ход (для В1 и В2) и дважды — «слабый». Возьмём верхнюю границу S с запасом: 30 × 42 × 2 = 960. Округлим до 1000.
Приведём полный код.
from functools import lru_cache
def m(s):
return s - 3, s - 5, s // 4
@lru_cache(None)
def g(s):
# Базовый случай
if s <= 30:
return 5
# Рекурсивные случаи
# Если есть хотя бы один ход в конечную позицию
if any(g(i) == 5 for i in m(s)):
return 1 # победа первым ходом
# Если все ходы ведут в В1
if all(g(i) == 1 for i in m(s)):
return -1 # поражение первым ходом
# Если есть хотя бы один ход в проигрышную позицию
if any(g(i) == -1 for i in m(s)):
return 2 # победа вторым ходом
# Если все ходы ведут в В1 или В2
if all(g(i) > 0 for i in m(s)):
return -2 # поражение первым ходом
return 0 # неопределённый случай
for s in range(31, 1000):
if g(s) == -1:
print(s)
Вывод программы:
Ответом на задание № 19 будет 124, на задание № 20 — 127 и 128, на задание № 21 — 132.
Как видим, в коде изменились функция ходов m(s), базовый случай и границы цикла при переборе начального количества камней.
Задача 3. Две кучи камней
Подход к решению прежний, но, поскольку в задании присутствует две кучи камней, код необходимо адаптировать. Добавим в функции второй аргумент.
Для поиска ответа на задание № 19, в котором речь идёт о неудачном ходе, заменим функцию all() для поиска позиций проигрышных за один ход на any(), поскольку нам подойдут позиции, из которых хотя бы один ход проигрышный.
from functools import lru_cache
def m(s, t):
return (s + 1, t), (s * 3, t), (s, t + 1), (s, t * 3)
@lru_cache(None)
def g(s, t):
# Базовый случай
if s + t >= 65:
return 5
# Рекурсивные случаи
# Если есть хотя бы один ход в конечную позицию
if any(g(i, j) == 5 for i, j in m(s, t)):
return 1 # победа первым ходом
# Если все ходы ведут в В1
if any(g(i, j) == 1 for i, j in m(s, t)):
return -1 # поражение первым ходом
# Если есть хотя бы один ход в проигрышную позицию
if any(g(i, j) == -1 for i, j in m(s, t)):
return 2 # победа вторым ходом
# Если все ходы ведут в В1 или В2
if all(g(i, j) > 0 for i, j in m(s, t)):
return -2 # поражение первым ходом
return 0 # неопределённый случай
for s in range(1, 59):
if g(6, s) == -1:
print(s)
Вывод программы:
Минимальное значение S = 7.
Для ответа на другие вопросы требуется вернуть all(), поскольку иначе нарушается стратегия игроков.
from functools import lru_cache
def m(s, t):
return (s + 1, t), (s * 3, t), (s, t + 1), (s, t * 3)
@lru_cache(None)
def g(s, t):
# Базовый случай
if s + t >= 65:
return 5
# Рекурсивные случаи
# Если есть хотя бы один ход в конечную позицию
if any(g(i, j) == 5 for i, j in m(s, t)):
return 1 # победа первым ходом
# Если все ходы ведут в В1
if all(g(i, j) == 1 for i, j in m(s, t)):
return -1 # поражение первым ходом
# Если есть хотя бы один ход в проигрышную позицию
if any(g(i, j) == -1 for i, j in m(s, t)):
return 2 # победа вторым ходом
# Если все ходы ведут в В1 или В2
if all(g(i, j) > 0 for i, j in m(s, t)):
return -2 # поражение первым ходом
return 0 # неопределённый случай
for s in range(1, 59):
if g(6, s) == 2:
print(s)
Вывод программы:
Ответы на задания: 19 — 7, 20 — 10 и 19, 21 — 18.
Заключение
Рекурсивный подход к решению задач на теорию игр на ЕГЭ по информатике демонстрирует баланс между лаконичностью кода и глубиной алгоритмического мышления. На примере рассмотренных заданий видно, что рекурсия позволяет:
- точно моделировать логику игры — структура кода напрямую отражает правила и стратегии (выигрышные и проигрышные позиции)
- сокращать объём кода по сравнению с итеративными методами — ключевые случаи (В1, П1, В2, П2) описываются компактными блоками с понятной семантикой
- сохранять связь с аналитическим решением — код читается как формализованная запись рассуждений, что упрощает проверку и отладку
- адаптироваться к разным условиям задач — изменение правил (ходы, критерии победы, количество куч) требует лишь корректировки функций
m()и базового случая, не затрагивая общую логику
Ключевые технические приёмы, повышающие эффективность рекурсивного решения:
-
мемоизация (через @lru_cache) устраняет избыточные вычисления, делая алгоритм практически применимым даже к большим диапазонам начальных позиций
-
использование
any()иall()позволяет кратко выразить логические условия (например, «существует хотя бы один выигрышный ход») -
чёткое разделение базового и рекурсивного случаев гарантирует корректность завершения рекурсии и предотвращает переполнение стека
Ограничения метода: -
без мемоизации рекурсия может быть крайне медленной из‑за многократного пересчёта одних и тех же позиций
-
в задачах с очень большими числами (тысячи и более) даже оптимизированная рекурсия может уступать динамическому программированию в скорости
Вывод
Рекурсивный метод — это мощное и элегантное средство для решения задач по теории игр в ЕГЭ по информатике. Он особенно ценен:
- на этапе обучения (помогает понять структуру задачи)
- при необходимости быстро реализовать решение с минимальной вероятностью ошибок
- в случаях, где требуется гибкость при изменении условий
Для максимальной эффективности важно:
- Всегда определять базовый случай (условие остановки)
- Использовать мемоизацию для оптимизации
- Тщательно проверять граничные условия (начальные и конечные позиции)
Таким образом, рекурсия не только даёт правильный ответ, но и служит инструментом для развития алгоритмического мышления, необходимого как на экзамене, так и в дальнейшем изучении программирования.
Рекомендуем решить подборки задач для практики:
- задачи с одной кучей
- задачи с двумя кучами