На ЕГЭ по информатике задания 19–21 проверяют умение анализировать выигрышные стратегии в играх с двумя игроками. Обычно их решают таблицей или деревом, но есть более универсальный способ — написать рекурсивную программу. Такой код сам перебирает все возможные ходы и помечает позиции как выигрышные или проигрышные. В этой статье разберём эту технику на двух типовых примерах — с одной кучей камней и с двумя кучами.
Термины, которые будем использовать: удачный/неудачный ход, выигрышная стратегия.
Для начала разберём идею написания нашего кода: мы, как и при решении руками, будем запоминать удачные клетки, из которых сразу будет победа, после чего каждый раз отталкиваться от них.
Если есть какая-то точка, из которой мы сразу можем победить (хотя бы один из ходов даёт победу), то эту точку мы называем P1. Именно из такой точки Петя может победить одним ходом.
V1 будем называть такую точку, которая ведёт в P1 при всех ходах. Такая точка будет проигрышной, и из-за неё Ваня может выиграть при любом первом ходе Пети.
P2 — точка, в которой победит Петя своим вторым ходом, из неё хотя бы одним ходом можно попасть в V1.
Для V2 мы будем рассматривать комбинацию событий, так как мы не знаем, когда в зависимости от условий Ваня выигрывает первым ходом, а когда вторым. Не все, но несколько примеров таких случаев представлены в схемах.
Типовые задания на одну и две кучи камней
Задание 1 (ЕГЭ 2023)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два или три камня или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17, 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 41 или больше камней.
В начальный момент в куче было S камней; 1 ≤ S ≤ 40.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Выполните следующие задания.
Во всех случаях обосновывайте свой ответ.
Задание 19
а) Укажите количество таких значений числа S, при которых Петя может выиграть в один ход.
б) Укажите два таких значения S, при которых Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20
Укажите максимальное и минимальное значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для каждого указанного значения S опишите выигрышную стратегию Пети.
Задание 21
Укажите минимальное значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. [i]
Напишем функцию, где внутри массива m находятся возможные ходы, которые бы мы могли сделать при изначальном количестве камней h. После этого постепенно начнём рассматривать случаи:
- Победа сразу же, если камней в куче оказалось 41 и больше.
- Победа Пети, если каким-то ходом он смог попасть в ту точку, которую мы обозначили WIN. Ему достаточно хотя бы одной из них, поэтому прописываем условие через or.
- Победа Вани получится, только если при любом ходе Ваня попадёт в клетку P1, значит, прописываем ходы через and.
- После Петя сможет выиграть своим ходом, если он пойдёт хотя бы из одного из ходов из клетки V1, прописываем через or.
- Чтобы Ваня выиграл своим первым или вторым ходом, начнём разбирать варианты через and и or, у него обязательно должны быть ходы и из точек P1, и P2. Заметим, что при наибольшем ходе *3 Ваня сможет выиграть только из точек P1, иначе он будет всегда выигрывать только своим вторым ходом.
Вспомним о некоторых встроенных функциях, которые позволят нам выполнить те же действия, но короче:
- any используется, если нам нужно, чтобы хотя бы одно число удовлетворяло условию;
- all — наоборот, когда нужно, чтобы каждое число удовлетворяло условию.
def g(h):
m = [h * 3, h + 3, h + 2] # наши возможные ходы, начинаем писать от самого большого количества к самому маленькому
if h >= 41: return ‘WIN’
if any(g(x) == ‘WIN’ for x in m): return ‘P1’ # если любой ход Пети из массива m принёс ему победу 1-м ходом
if all(g(x) == ‘P1’ for x in m): return ‘V1’ # если все ходы Вани из массива m привели его в точку P1
if any(g(x) == ‘V1’ for x in m): return ‘P2’ # если любой ход Пети привёл его в точку V1
if all(g(x) == ‘P1’ or g(x) == ‘P2’ for x in m): return ‘V2’ # если для любого хода Вани нашлись ходы, при которых он пойдёт из точки P1 и в каком-то случае/ях из P2
for h in range(1, 41):
print(h, g(h))
Ответ
19: а) 27; б) 12, 13
20: 4, 11
21: 7
Задание 2
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 62. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах будет 62 или больше камней. В начальный момент в первой куче было 7 камней, во второй куче — S камней; 1 ≤ S ≤ 54.
Задание 19
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20
Найдите минимальное значение S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Задание 21
Найдите два минимальных значения S, при которых одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания. [i]
Теперь вместо одного числа в качестве переменной h мы будем записывать в функцию кортеж, после чего строкой a, b = h делить его на два значения: a — количество камней в первой куче, а b — во второй. Придётся прописать чуть больше возможных ходов по увеличению куч, как мы это и делали руками/таблицами.
Также заметим, что вопрос в 19-м задании отличается от того, что мы разобрали до этого, поэтому для него напишем отдельный код: неудачным ходом Пети считается такой ход, после которого Ваня может выиграть своим первым ходом, поэтому пропишем это через any/or.
# Для заданий 20–21:
from functools import *
@lru_cache(None)
def g(h):
a, b = h # разбиваем введённый кортеж h на 2 числа
if a + b >= 62: return ‘WIN’ # сумма камней в двух кучах
m = [(a + 2, b), (a, b + 2), (a * 2, b), (a, b * 2)] # наши возможные ходы
if any(g(x) == ‘WIN’ for x in m): return ‘P1’
if all(g(x) == ‘P1’ for x in m): return ‘V1’
if any(g(x) == ‘V1’ for x in m): return ‘P2’
if all(g(x) == ‘P1’ or g(x) == ‘P2’ for x in m): return ‘V2’
print(’20:’, [i for i in range(1, 200) if g((7, i)) == ‘P2′])
print(’21:’, [i for i in range(1, 200) if g((7, i)) == ‘V2’])
# Для задания 19:
def g(h):
a, b = h
if a + b >= 62: return ‘WIN’
m = [(a + 2, b), (a, b + 2), (a * 2, b), (a, b * 2)]
if any(g(x) == ‘WIN’ for x in m): return ‘P1’
if any(g(x) == ‘P1’ for x in m): return ‘V1’ # подходит ЛЮБОЙ ход Пети, который мог бы принести победу Ване
print(’19:’, [i for i in range(1, 200) if g((7, i)) == ‘V1’])
Ответ
19: 14
20: 23
21: 21, 24
Заключение
Рекурсивная функция с метками WIN, P1, V1, P2, V2 и операторами any/all полностью заменяет ручное построение дерева игры. Главное — правильно задать список ходов и условие окончания, а код под любые задачи пишется по единому шаблону. Чтобы закрепить тему, рекомендуем решить несколько аналогичных заданий в «100балльном банке».
