В предыдущей статье мы написали две программы для игры с одной кучей: пошаговую с функциями win и lose и короткую рекурсивную. Теперь перенесём оба подхода на игры с двумя кучами.
Повторять общие правила игры не будем. Разберём только изменения в коде: как хранить две кучи, как строить ходы и как проверять победный порог.
Сначала изменим пошаговые функции и убедимся, что смысл позиций В1, П1, В2 и П2 сохранился. Затем перепишем рекурсивную функцию. Реальные примеры решим только рекурсией.
Изменения в коде с функциями win и lose
Позиция из двух куч
В игре с одной кучей позицию описывало число x. Теперь нужны два числа: a — количество камней в первой куче, b — количество камней во второй куче.
Если за ход можно прибавить 1 или удвоить одну выбранную кучу, из позиции (a, b) получаются четыре новые позиции:
def moves(a, b):
return ((a + 1, b),
(a * 2, b),
(a, b + 1),
(a, b * 2))
В первых двух строках меняется первая куча, а во вторых двух — вторая. За один ход изменяется только одна куча, потому что игрок выбирает одну команду и применяет её к одной куче.
Каждый результат записывается парой. Поэтому при переборе ходов пару нужно распаковать в две переменные: next_a и next_b.
for next_a, next_b in moves(a, b):
# next_a и next_b описывают новую позицию
Условие окончания игры
Чаще всего игра заканчивается, когда сумма камней в двух кучах достигает заданного значения. Если победный порог равен 59, функция finish выглядит так:
def finish(a, b):
return a + b >= 59
Функция получает оба размера и складывает их. В остальном её роль не изменилась: она возвращает True для конечной позиции и False для позиции, из которой игру ещё можно продолжать.
Позиции В1
В позиции В1 текущий игрок может закончить игру одним ходом. Мы перебираем четыре новые пары и возвращаем True, как только одна из них оказывается конечной.
def win1(a, b):
if finish(a, b):
return False
for next_a, next_b in moves(a, b):
if finish(next_a, next_b):
return True
return False
По сравнению с одной кучей изменилась только запись позиции. Вместо y цикл получает next_a и next_b, а функция finish вызывается с двумя аргументами.
Позиции П1
В позиции П1 любой ход текущего игрока передаёт сопернику В1. Поэтому проверяем каждый результат функции moves.
def lose1(a, b):
if finish(a, b):
return False
for next_a, next_b in moves(a, b):
if not win1(next_a, next_b):
return False
return True
Если хотя бы один ход ведёт не в В1, текущий игрок выберет эту ветвь и разрушит стратегию соперника. Поэтому функция сразу возвращает False.
Позиции В2
В позиции В2 нельзя победить сразу, но существует ход в П1. Проверки остаются теми же, только каждая функция получает два размера куч.
def win2(a, b):
if finish(a, b) or win1(a, b):
return False
for next_a, next_b in moves(a, b):
if lose1(next_a, next_b):
return True
return False
Позиции П2
В позиции П2 любой ход передаёт сопернику В1 или В2. Позицию П1 исключаем, потому что в ней соперник гарантированно выигрывает уже первым ходом.
def lose2(a, b):
if finish(a, b) or lose1(a, b):
return False
for next_a, next_b in moves(a, b):
if not (win1(next_a, next_b)
or win2(next_a, next_b)):
return False
return True
Итак, логика функций win1, lose1, win2 и lose2 не зависит от количества куч. Меняется только представление позиции и число возможных ходов.
Две формулировки задания 19
Если Ваня должен выиграть после любого хода Пети, начальная позиция относится к П1. Для неё используем lose1.
answer19 = min(S for S in values
if lose1(first_heap, S))
Фраза «после неудачного хода Пети» означает другое. Петя уже выбрал одну неудачную ветвь, поэтому достаточно доказать существование такого хода.
def after_bad_move(a, b):
for next_a, next_b in moves(a, b):
if (not finish(next_a, next_b)
and win1(next_a, next_b)):
return True
return False
Проверка not finish не позволяет засчитать ход, которым Петя сам закончил игру. Функция win1 проверяет, сможет ли Ваня победить одним ответным ходом.
Рекурсивное решение
Теперь перенесём рекурсивную функцию из предыдущей статьи. Она получает размеры обеих куч и количество оставшихся ходов: f(a, b, moves_left).
Число аргументов увеличилось, но порядок работы не изменился: проверяем конец игры, затем нулевую глубину, строим следующие позиции и выбираем между any и all.
Проверяем конец игры
def f(a, b, moves_left):
if a + b >= 59:
return moves_left % 2 == 0
if moves_left == 0:
return False
В первой строке складываются обе кучи. Чётныйmoves_left означает, что победный ход сделал игрок, чью стратегию мы проверяем.
Проверка победы снова стоит раньше нулевой глубины. Иначе программа не засчитает ход, который достиг порога на последнем разрешённом уровне.
Формируем список next_results
В игре с двумя кучами список содержит четыре рекурсивных вызова. В каждом из них меняется только одна куча, а moves_left уменьшается на единицу.
Каждый элемент списка отвечает на вопрос: сохраняется ли нужная стратегия после конкретного хода. Порядок строк повторяет порядок ходов из функции moves.
На ходе игрока, чью победу мы проверяем, достаточно одного удачного продолжения, поэтому используется any. На ходе соперника стратегия должна выдержать все ответы, поэтому используется all.
Условие (moves_left + 1) % 2 == 0 проверяет, что moves_leftнечётно. Эта часть функции полностью совпадает с программой для одной кучи.
Вся функция выглядит следующим образом:
def f(a, b, moves_left):
if a + b >= 59:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f(a + 1, b, moves_left - 1),
f(a * 2, b, moves_left - 1),
f(a, b + 1, moves_left - 1),
f(a, b * 2, moves_left - 1)]
return (any(next_results)
if (moves_left + 1) % 2 == 0
else all(next_results))
Для задания 20 используем глубины 3 и 1, а для задания 21 — глубины 4 и 2. Первая глубина проверяет нужный срок победы, вторая исключает более ранний срок.
Рекурсия для неудачного хода Пети
Обычная функция f проверяет гарантированную стратегию. Но после неудачного хода Пети нам достаточно найти одну ветвь Пети и один победный ответ Вани.
Поэтому для такой формулировки создадим отдельную функцию f19. В ней на обоих уровнях используется any.
def f19(a, b, moves_left):
if a + b >= 59:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f19(a + 1, b, moves_left - 1),
f19(a * 2, b, moves_left - 1),
f19(a, b + 1, moves_left - 1),
f19(a, b * 2, moves_left - 1)]
return any(next_results)
Вызов f19(first_heap, S, 2) рассматривает один ход Пети и один ответ Вани. Проверка чётности не засчитывает ветвь, в которой Петя сам достиг порога первым ходом.
Пример 1
Применим рекурсивную функцию для решения такого задания:
Задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество суммарное камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах находится 59 камень или больше.
В начальный момент в первой куче было 5 камней, во второй куче — S камней; 1 ≤ S ≤ 53.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.
В первой куче находится 5 камней, во второй — S, где 1 ≤ S ≤ 53. За ход можно прибавить 1 или удвоить одну выбранную кучу. Победная сумма равна 59.
В задании 19 Ваня выиграл после неудачного хода Пети, поэтому для него используем f19. Задания 20 и 21 решаем обычной функцией f.
def f(a, b, moves_left):
if a + b >= 59:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f(a + 1, b, moves_left - 1),
f(a * 2, b, moves_left - 1),
f(a, b + 1, moves_left - 1),
f(a, b * 2, moves_left - 1)]
return (any(next_results)
if (moves_left + 1) % 2 == 0
else all(next_results))
def f19(a, b, moves_left):
if a + b >= 59:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f19(a + 1, b, moves_left - 1),
f19(a * 2, b, moves_left - 1),
f19(a, b + 1, moves_left - 1),
f19(a, b * 2, moves_left - 1)]
return any(next_results)
values = range(1, 54)
answer19 = min(S for S in values if f19(5, S, 2))
answer20 = [S for S in values
if f(5, S, 3) and not f(5, S, 1)][:2]
answer21 = min(S for S in values
if f(5, S, 4) and not f(5, S, 2))
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
Программа выводит: задание 19 — 14; задание 20 — 24 и 26; задание 21 — 23.
При S = 14 Петя может удвоить вторую кучу и получить (5, 28). Ваня снова удваивает её, получает (5, 56) и доводит сумму до 61.
Здесь показана одна неудачная ветвь Пети. Доказывать победу Вани после каждого первого хода не требуется, потому что условие задания 19 этого не утверждает.
Значения 24 и 26 дают Пете победу вторым ходом, но не первым. При S = 23 Ваня гарантированно побеждает своим первым или вторым ходом.
Пример 2
Приведём решение еще одного задания:
Задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в три раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 136. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах находится 136 камней или больше.
В начальный момент в первой куче было 2 камня, во второй куче — S камней; 1 ≤ S ≤ 132.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.
В первой куче находится 2 камня, 1 ≤ S ≤ 132. За ход можно прибавить 2 или утроить одну выбранную кучу. Победная сумма равна 136.
Меняем победный порог, четыре рекурсивных перехода и диапазон S. Формулы ответов остаются прежними.
def f(a, b, moves_left):
if a + b >= 136:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f(a + 2, b, moves_left - 1),
f(a * 3, b, moves_left - 1),
f(a, b + 2, moves_left - 1),
f(a, b * 3, moves_left - 1)]
return (any(next_results)
if (moves_left + 1) % 2 == 0
else all(next_results))
def f19(a, b, moves_left):
if a + b >= 136:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f19(a + 2, b, moves_left - 1),
f19(a * 3, b, moves_left - 1),
f19(a, b + 2, moves_left - 1),
f19(a, b * 3, moves_left - 1)]
return any(next_results)
values = range(1, 133)
answer19 = min(S for S in values if f19(2, S, 2))
answer20 = [S for S in values
if f(2, S, 3) and not f(2, S, 1)][:2]
answer21 = min(S for S in values
if f(2, S, 4) and not f(2, S, 2))
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
Программа выводит: задание 19 — 15; задание 20 — 42 и 43; задание 21 — 41.
При S = 15 существует неудачный ход Пети, после которого Ваня сразу достигает суммы 136. Значения 42 и 43 подходят заданию 20, а 41 — заданию 21.
Пример 3
Для закрепления рассмотрим еще одно задание:
Задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество суммарное камней в кучах становится не менее 123. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах находится 123 камней или больше.
В начальный момент в первой куче было 9 камней, во второй куче — S камней; 1 ≤ S ≤ 113.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
В первой куче находится 9 камней, 1 ≤ S ≤ 113. За ход можно прибавить 1 или удвоить одну выбранную кучу. Победная сумма равна 123.
def f(a, b, moves_left):
if a + b >= 123:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f(a + 1, b, moves_left - 1),
f(a * 2, b, moves_left - 1),
f(a, b + 1, moves_left - 1),
f(a, b * 2, moves_left - 1)]
return (any(next_results)
if (moves_left + 1) % 2 == 0
else all(next_results))
def f19(a, b, moves_left):
if a + b >= 123:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f19(a + 1, b, moves_left - 1),
f19(a * 2, b, moves_left - 1),
f19(a, b + 1, moves_left - 1),
f19(a, b * 2, moves_left - 1)]
return any(next_results)
values = range(1, 114)
answer19 = min(S for S in values if f19(9, S, 2))
answer20 = [S for S in values
if f(9, S, 3) and not f(9, S, 1)][:2]
answer21 = min(S for S in values
if f(9, S, 4) and not f(9, S, 2))
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
Программа выводит: задание 19 — 29; задание 20 — 52 и 56; задание 21 — 51.
Правая граница range равна 114, потому что значение 113 должно попасть в перебор. При S = 29 существует нужная ветвь задания 19, а 52, 56 и 51 дают ответы заданий 20 и 21.
Шаблон решения
В шаблоне нужно заменить условие окончания игры, четыре хода, границы S и начальное количество камней в первой куче.
def f(a, b, moves_left):
if *1:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f(*2, moves_left - 1),
f(*3, moves_left - 1),
f(*4, moves_left - 1),
f(*5, moves_left - 1)]
return (any(next_results)
if (moves_left + 1) % 2 == 0
else all(next_results))
def f19(a, b, moves_left):
if *1:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f19(*2, moves_left - 1),
f19(*3, moves_left - 1),
f19(*4, moves_left - 1),
f19(*5, moves_left - 1)]
return any(next_results)
values = range(*6, *7)
answer19 = min(S for S in values if f19(*8, S, 2))
answer20 = [S for S in values
if f(*8, S, 3) and not f(*8, S, 1)][:2]
answer21 = min(S for S in values
if f(*8, S, 4) and not f(*8, S, 2))
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
Здесь:
*1 — условие окончания игры;
*2–*5 — пары аргументов после четырёх ходов;
*6 и *7 — границы S;
*8 — начальное количество камней в первой куче.
Функция f19 нужна только для формулировки «после неудачного хода Пети». Если Ваня должен победить после любого хода Пети, в answer19 используйте f(*8, S, 2).
Итоги
При переходе к двум кучам позиция получает два значения: a и b. Функция moves возвращает пары, а finish обычно проверяет суммуa + b. Логика позиций В1, П1, В2 и П2 остаётся прежней.
В рекурсивной функции добавляется размер второй кучи и четыре вызова в next_results. Проверки конца игры, нулевой глубины и выбор между any и all работают так же, как в игре с одной кучей.
Всегда следите, чтобы за один ход изменялась только одна куча. Проверяйте все команды, победный порог и правую границу range.
В задании 19 различайте фразы «при любом ходе» и «после неудачного хода». В первом случае нужна гарантия по всем ветвям, а во втором достаточно существования лишь одной подходящей ветви.
Помните, что finish проверяется раньше moves_left == 0. В заданиях 20 и 21 исключайте победу на меньшей глубине с помощью not f.
На этом мы закончили программный разбор заданий 19–21 с одной и двумя кучами. Попрактиковаться в решении заданий этого типа можно в нашем тренажёре.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
