В предыдущей статье мы научились решать задания 19–21 вручную. Мы строили дерево игры и последовательно находили позиции В1, П1, В2 и П2.
Ручной способ помогает понять стратегию, но на большом дереве приходится держать в голове много ветвей. Один пропущенный ход может изменить ответ, а проверка каждой позиции занимает время.
Программа выполняет ту же разметку автоматически. Сначала запишем знакомые уровни отдельными функциями, затем применим их к заданиям ЕГЭ и соберём общий алгоритм в одну рекурсивную функцию.
Что нужно помнить об игре
Участники и порядок ходов
Петя и Ваня играют с одной кучей камней. Они ходят по очереди, и первый ход всегда делает Петя. За ход игрок выполняет одну из команд, перечисленных в условии.
После каждого хода проверяется условие окончания игры. Если количество камней достигло заданного порога, игра сразу заканчивается, а сделавший последний ход игрок побеждает.
В играх на увеличение победный порог нужно достичь или превысить. В играх на уменьшение, наоборот, требуется получить не больше указанного числа.
Начальное число S
Буквой S обозначают количество камней перед первым ходом Пети. Именно это начальное значение требуется найти в ответе.
После начала игры количество камней меняется. Поэтому в функциях будем называть текущее значение x, а букву S оставим для перебора начальных позиций.
Выигрышная стратегия
Выигрышная стратегия гарантирует победу при любых допустимых действиях соперника. Недостаточно показать одну удобную партию: нужно учесть и самый невыгодный ответ другого игрока.
Поэтому в одних позициях мы ищем хотя бы один удачный ход, а в других проверяем все ходы. Это различие и станет основой программы.
Что ищут задания 19, 20 и 21
Во всех трёх заданиях используются одни правила и одно начальное значение S. Меняется только игрок, который должен победить, и допустимое число ходов.
Задание 19: Петя не выигрывает сразу, а Ваня побеждает первым ходом после любого хода Пети. Это позиция П1.
Задание 20: Петя не выигрывает сразу, но может гарантированно победить своим вторым ходом. Это позиция В2.
Задание 21: Ваня гарантированно побеждает первым или вторым ходом, но победа первым ходом ему не гарантирована. Это позиция П2.
Алгоритм решения
Сначала возьмём простой пример из ручного разбора. В куче находится S камней. За один ход можно прибавить 2 или прибавить 5 камней.
Побеждает игрок, после хода которого в куче становится 20 камней или больше. Значения 20 и выше уже конечные: из них следующий ход делать нельзя.
На этой игре выведем программу по шагам. Когда смысл каждой функции станет понятен, заменим только правила хода и порог и решим настоящее задание ЕГЭ.
Уровни позиций
Вспомним, наши условные обозначения позиций.
Буква В обозначает выигрышную позицию для игрока, которому предстоит ход. Буква П обозначает позицию, из которой соперниксможет навязать победу (его победу, само собой, а не текущего игрока).
В1 — существует ход, который сразу завершает игру.
П1 — каждый возможный ход передаёт сопернику позицию В1.
В2 — победы за один ход нет, но существует ход в П1.
П2 — позиция не относится к П1, а каждый ход передаёт сопернику В1 или В2.
Описание одного хода и конца игры
Функция moves получает текущее количество камней x и возвращает все результаты одного хода. Функция finish проверяет, закончилась ли игра. В нашем случае в moves будут ходы «+2» и «+5». В условием завершения всей игры будет неравенство x >= 20.
def moves(x):
return x + 2, x + 5
def finish(x):
return x >= 20
Например, moves(10) возвращает 12 и 15. Вызов finish(20) возвращает True, а finish(19) — False.
Позиции В1
В позиции В1 текущему игроку достаточно одного победного хода. Поэтому перебираем результаты и возвращаем True, как только среди них встретится конечная позиция.
def win1(x):
if finish(x):
return False
for y in moves(x):
if finish(y):
return True
return False
Проверка finish(x) исключает уже завершённую игру. Например, win1(15) возвращает True: ход +5 даёт 20 камней.
В этой игре к В1 относятся значения от 15 до 19. Из каждого можно получить не менее 20 камней одним ходом.
Позиции П1
В позиции П1 текущий игрок проигрывает при любом своём ходе. Значит, каждый результат должен относиться к В1 для соперника.
def lose1(x):
if finish(x):
return False
for y in moves(x):
if not win1(y):
return False
return True
Если встретился хотя бы один ход не в В1, функция возвращает False: текущий игрок выберет эту ветвь и разрушит стратегию соперника.
Для x = 13 получаются 15 и 18. Обе позиции входят в В1, поэтому lose1(13) возвращает True. То же верно для x = 14.
Так программа повторяет ручную проверку задания 19: Петя не завершает игру, а после любого его хода Ваня выигрывает сразу.
Позиции В2
В позиции В2 текущий игрок ещё не может победить сразу. Однако среди его ходов существует переход в П1.
def win2(x):
if finish(x) or win1(x):
return False
for y in moves(x):
if lose1(y):
return True
return False
Сначала исключаем конечные позиции и В1. Затем ищем один ход в П1. Для учебной игры два наименьших значения В2 равны 8 и 9: ходом +5 Петя оставляет 13 или 14 камней.
Позиции П2
В позиции П2любой ход передаёт сопернику В1 или В2. Позицию П1 исключаем, потому что в ней соперник гарантированно выигрывает первым ходом.
def lose2(x):
if finish(x) or lose1(x):
return False
for y in moves(x):
if not (win1(y) or win2(y)):
return False
return True
Для x = 6 после ходов получаются 8 и 11. Обе позиции входят в В2, поэтому соперник гарантированно победит своим вторым ходом. Значит, lose2(6) возвращает True.
Вся программа
Соберём функции вместе. Ответы пока найдём обычным циклом, чтобы код показывал саму логику, а не новые конструкции Python.
def moves(x):
return x + 2, x + 5
def finish(x):
return x >= 20
def win1(x):
if finish(x):
return False
for y in moves(x):
if finish(y):
return True
return False
def lose1(x):
if finish(x):
return False
for y in moves(x):
if not win1(y):
return False
return True
def win2(x):
if finish(x) or win1(x):
return False
for y in moves(x):
if lose1(y):
return True
return False
def lose2(x):
if finish(x) or lose1(x):
return False
for y in moves(x):
if not (win1(y) or win2(y)):
return False
return True
answer19 = None
answer20 = []
answer21 = None
for S in range(1, 20):
if answer19 is None and lose1(S):
answer19 = S
if len(answer20) < 2 and win2(S):
answer20.append(S)
if answer21 is None and lose2(S):
answer21 = S
print('19:', answer19)
print('20:', answer20)
print('21:', answer21)
Перебор идёт по возрастанию. Поэтому первое найденное значение подходит для заданий 19 и 21, а первые два элемента answer20 дают ответ задания 20.
Программа выводит 13; 8 и 9; 6. Это те же значения, которые мы получили ручной разметкой во второй статье.
Рекурсивное решение
Мы уже решили учебную игру с помощью функций win1, lose1, win2 и lose2. Теперь обойдём то же дерево одной рекурсивной функцией. Правила не меняются: за ход можно прибавить 2 или 5, а победный порог равен 20.
Функция будет получать текущее количество камней x и число оставшихся ходов moves_left. При каждом рекурсивном вызове количество камней изменяется, а moves_leftуменьшается на единицу.
Сразу запишем всю функцию целиком, а потом разберём её по частям:
Разбираем сверху вниз. Первая проверка определяет, закончилась ли игра. Если x уже не меньше 20, победитель был определён предыдущим ходом и строить новые ветви нельзя. Это та же самая проверка, что и в finish(x) ранее.
Выражение moves_left % 2 == 0 проверяет, нужный ли игрок сделал последний ход. Чётный остаток означает его победу, поэтому функция возвращает True. Нечётный остаток означает победу соперника.
Проверка окончания игры стоит раньше, чем moves_left == 0. Иначе функция не засчитает победу, полученную последним разрешённым ходом.
Если порог ещё не достигнут, но moves_left равно нулю, отведённые ходызакончились. Нужной победы за это время не произошло, поэтому функция возвращает False.
Как формируется список next_results
После двух базовых проверок функция строит следующие ходы. В учебной игре из x можно перейти в x + 2 или x + 5, поэтому в списке находятся два рекурсивных вызова.
Каждый вызов возвращает True или False. Первое значение показывает, сохраняется ли нужная стратегия после хода +2, а второе — после хода +5.
Например, вызов f(13, 2) создаёт список из результатов f(15, 1) и f(18, 1). Внутри каждого вызова снова проверяется конец игры и при необходимости строятся следующие ходы.
Параметр moves_left уменьшается на единицу, потому что один ход уже сделан. Так функция постепенно спускается по дереву и обязательно достигает конечной позиции или нулевой глубины.
Роль any и all
Если ходит игрок, чью победу мы проверяем, ему достаточно одного (любого = any) удачного продолжения. В этом случае any возвращает True, когда хотя бы один элемент next_results равен True.
any([False, True]) # True
Если ходит соперник, стратегия должна выдержать любой его ход. То есть нужно проверять всё действия соперника, как мы это обсуждали в прошлой статье.
В этом случае all возвращает True, только когда все элементы next_results равны True.
all([True, True]) # True
В нашей записи ход нужного игрока соответствует нечётномуmoves_left. Условие (moves_left + 1) % 2 == 0 как раз проверяет, что moves_leftнечётно. Тогда используется any; при чётном остатке используется all.
Для задания 19 вызывается f(S, 2). Сначала ходит Петя — соперник искомого победителя Вани, поэтому проверяются все ходы Пети. Затем moves_left становится равным 1, и Ване достаточно одного победного ответа.
Разбираем вызов f(13, 2)
Из 13 Петя может получить 15 или 18. Поэтому верхний вызов должен убедиться, что Ваня справится с обеими позициями: результат вычисляется функцией all.
Из 15 Ваня может получить 17 или 20. Один из ходов завершает игру, поэтому f(15, 1) возвращает True благодаря any.
Из 18 Ваня получает 20 или 23. Оба хода завершают игру, поэтому f(18, 1) также возвращает True.
Список верхнего вызова равен [True, True]. Функция all возвращает True, поэтому f(13, 2) подтверждает: после любого хода Пети Ваня победит своим первым ходом.
Формируем ответы
Сначала сохраним диапазон начальных значений. Затем отдельно вычислим ответы трёх заданий и только после этого передадим готовые значения функции print.
values = range(1, 20)
answer19 = min(
S for S in values
if f(S, 2)
)
answer20 = [
S for S in values
if f(S, 3) and not f(S, 1)
][:2]
answer21 = min(
S for S in values
if f(S, 4) and not f(S, 2)
)
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
В answer19 используется генераторное выражение: оно передаёт функции min подходящие значения S по одному. Функция min выбирает из них наименьшее.
В answer20 используется списочное включение. Квадратные скобки создают список всех подходящих S, а срез [:2] оставляет первыедва значения. Поэтому диапазон должен идти по возрастанию.
Условие f(S, 3) проверяет победу Пети не позднее второго хода, а not f(S, 1) исключает победу первым ходом. Аналогично для задания 21 глубина 2 исключается из глубины 4.
И весь код программы выглядит так:
def f(x, moves_left):
if x >= 20:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f(x + 2, moves_left - 1),
f(x + 5, moves_left - 1)]
return (any(next_results)
if (moves_left + 1) % 2 == 0
else all(next_results))
values = range(1, 20)
answer19 = min(
S for S in values
if f(S, 2)
)
answer20 = [
S for S in values
if f(S, 3) and not f(S, 1)
][:2]
answer21 = min(
S for S in values
if f(S, 4) and not f(S, 2)
)
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
Программа выводит 13; 8 и 9; 6. Мы получили те же ответы, что и при пошаговой разметке позиций.
Сравнение двух подходов
Функции win1, lose1, win2 и lose2 лучше использовать при первомзнакомстве с теорией игр. Их названия показывают, какую позицию мы ищем, а код почти дословно повторяет ручные рассуждения.
Такой подход также удобен, когда нужно подробно доказать ответ. Можно отдельно проверить В1, П1, В2 и П2 и увидеть, на каком уровне появилась ошибка.
Рекурсивный код короче. В нём одна функция обходит дерево на нужную глубину, поэтому при переходе к новому условию требуется заменить ходы, победный порог и диапазон S.
На экзамене рекурсия обычно экономит время, если вы уверенно понимаете чётность глубины, порядок базовых проверок и выбор между any и all. Если эта логика путается, безопаснее вернуться к пошаговым функциям.
Лучше всего будет комбинировать оба способа: сначала решить через рекурсию, а потом проверить функциями win/lose или вообще вручную.
Пример 1
Давайте проверим оба кода на реальном задаии ЕГЭ:
Задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня либо увеличить количество камней в куче в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда количество камней в куче становится не менее 67. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 67 камней или больше. В начальный момент в куче было S камней; 1 ≤ S ≤ 66.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом
Задание 20
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.
В куче находится S камней, 1 ≤ S ≤ 66. За ход можно прибавить 1, прибавить 3 или удвоить количество камней. Игра заканчивается, когда в куче становится не меньше 67 камней. Начнём с первого подхода. Выпишем все ходы:
def moves(x):
return x + 1, x + 3, x * 2
В функции finish определим граничное значение для победы (не меньше 67):
def finish(x):
return x >= 67
Функции win/lose не меняются:
def win1(x):
if finish(x):
return False
for y in moves(x):
if finish(y):
return True
return False
def lose1(x):
if finish(x):
return False
for y in moves(x):
if not win1(y):
return False
return True
def win2(x):
if finish(x) or win1(x):
return False
for y in moves(x):
if lose1(y):
return True
return False
def lose2(x):
if finish(x) or lose1(x):
return False
for y in moves(x):
if not (win1(y) or win2(y)):
return False
return True
Теперь формируем ответы. Главное не забыть указать верхнюю границу диапазона range:
answer19 = None
answer20 = []
answer21 = None
for S in range(1, 67):
if answer19 is None and lose1(S):
answer19 = S
if len(answer20) < 2 and win2(S):
answer20.append(S)
if answer21 is None and lose2(S):
answer21 = S
print('19:', answer19)
print('20:', answer20)
print('21:', answer21)
Целиком программа выглядит так:
def moves(x):
return x + 1, x + 3, x * 2
def finish(x):
return x >= 67
def win1(x):
if finish(x):
return False
for y in moves(x):
if finish(y):
return True
return False
def lose1(x):
if finish(x):
return False
for y in moves(x):
if not win1(y):
return False
return True
def win2(x):
if finish(x) or win1(x):
return False
for y in moves(x):
if lose1(y):
return True
return False
def lose2(x):
if finish(x) or lose1(x):
return False
for y in moves(x):
if not (win1(y) or win2(y)):
return False
return True
answer19 = None
answer20 = []
answer21 = None
for S in range(1, 67):
if answer19 is None and lose1(S):
answer19 = S
if len(answer20) < 2 and win2(S):
answer20.append(S)
if answer21 is None and lose2(S):
answer21 = S
print('19:', answer19)
print('20:', answer20)
print('21:', answer21)
Программа выводит: задание 19 — 33; задание 20 — 30 и 32; задание 21 — 29.
Для S = 33 после ходов Пети получаются 34, 36 и 66. Из каждой позиции Ваня завершает игру одним ходом: получает 68, 72 или 67 камней.
Из 30 Петя переходит в 33 ходом +3, а из 32 — ходом +1. Поэтому при S = 30 и S = 32 Петя гарантированно выигрывает своим вторым ходом.
При S = 29 Петя оставляет 30, 32 или 58 камней. После каждого его хода Ваня сохраняет стратегию победы своим первым или вторым ходом.
Перейдём к решению рекурсивной функцией. Сначала запишем условие окончания игры:
def f(x, moves_left):
if x >= 67:
return moves_left % 2 == 0
Далее идёт проверка, остались ли еще доступные ходы:
Сформируем ответы. Сначала пишем диапазон допустимого количества камней:
values = range(1, 67)
Вычисляем и выводим на экран все три ответа:
answer19 = min(
S for S in values
if f(S, 2)
)
answer20 = [
S for S in values
if f(S, 3) and not f(S, 1)
][:2]
answer21 = min(
S for S in values
if f(S, 4) and not f(S, 2)
)
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
Всё решение выглядит так:
def f(x, moves_left):
if x >= 67:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f(x + 1, moves_left - 1),
f(x + 3, moves_left - 1),
f(x * 2, moves_left - 1)]
return (any(next_results)
if (moves_left + 1) % 2 == 0
else all(next_results))
values = range(1, 67)
answer19 = min(
S for S in values
if f(S, 2)
)
answer20 = [
S for S in values
if f(S, 3) and not f(S, 1)
][:2]
answer21 = min(
S for S in values
if f(S, 4) and not f(S, 2)
)
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
Запускаем и получаем те же ответы: 33, 30 и 32, 29.
Пример 2
Далее так подробно останавливаться на разборе решения уже не будем. Использовать будем только рекурсивную функцию. На очереди такое задание:
Задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 3 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 40 камней за один ход можно получить кучу из 37, 35 или 10 камней.
Игра завершается, когда количество камней в куче становится не более 60. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 60 или менее камней. В начальный момент в куче было S камней, S ≥ 61.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
За ход можно вычесть 3, вычесть 5 или разделить количество камней на 4 с округлением вниз. Побеждает игрок, после хода которого в куче становится не больше 60 камней.
def f(x, moves_left):
if x <= 60:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f(x - 3, moves_left - 1),
f(x - 5, moves_left - 1),
f(x // 4, moves_left - 1)]
return (any(next_results)
if (moves_left + 1) % 2 == 0
else all(next_results))
values = range(61, 1000)
answer19 = min(S for S in values if f(S, 2))
answer20 = [S for S in values
if f(S, 3) and not f(S, 1)][:2]
answer21 = min(S for S in values
if f(S, 4) and not f(S, 2))
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
Программа выводит: задание 19 — 244; задание 20 — 247 и 248; задание 21 — 252.
Для S = 244 Петя оставляет 241, 239 или 61 камень. Из каждой позиции Ваня заканчивает игру одним ходом.
При S = 247 и S = 248 Петя переводит игру в позицию 244 или 245 и гарантирует победу следующим ходом. При S = 252 Ваня выигрывает своим первым или вторым ходом.
Пример 3
Завершаем наш разбор заданием со следующей формулировкой:
Задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
— добавить в кучу 2 камня;
— добавить в кучу 4 камня;
— увеличить количество камней в куче в 2 раза.
Например, из кучи в 20 камней за один ход можно получить кучу из 22, 24 или 40 камней.
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 125. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 125 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 124.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём
одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два
условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
За ход можно прибавить 2, прибавить 4 или удвоить количество камней. Игра заканчивается при 125 камнях, а начальное значение удовлетворяет условию 1 ≤ S ≤ 124.
def f(x, moves_left):
if x >= 125:
return moves_left % 2 == 0
if moves_left == 0:
return False
next_results = [f(x + 2, moves_left - 1),
f(x + 4, moves_left - 1),
f(x * 2, moves_left - 1)]
return (any(next_results)
if (moves_left + 1) % 2 == 0
else all(next_results))
values = range(1, 125)
answer19 = min(S for S in values if f(S, 2))
answer20 = [S for S in values
if f(S, 3) and not f(S, 1)][:2]
answer21 = min(S for S in values
if f(S, 4) and not f(S, 2))
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
Программа выводит: задание 19 — 61; задание 20 — 31 и 57; задание 21 — 55.
При S = 61 после любого хода Пети Ваня выигрывает сразу. Из 31 и 57 Петя переводит игру в П1, а при S = 55 после любого хода Пети у Вани остаётся выигрышная стратегия.
Шаблон решения
Выведем шаблон решения через рекурсивную функцию.
В типовой игре с одной кучей меняются победное условие, команды и диапазон S. Остальную часть программы можно использовать без изменения.
def f(x, 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)]
return (any(next_results)
if (moves_left + 1) % 2 == 0
else all(next_results))
values = range(*5, *6)
answer19 = min(S for S in values if f(S, 2))
answer20 = [S for S in values
if f(S, 3) and not f(S, 1)][:2]
answer21 = min(S for S in values
if f(S, 4) and not f(S, 2))
print('19:', answer19)
print('20:', *answer20)
print('21:', answer21)
Здесь:
*1 — условие окончания игры;
*2–*4 — новые значения x после разрешённых ходов;
*5 и *6 — границы перебора S.
Если команд не три, добавьте или удалите элементы списка next_results.
Итоги
Мы решили одну и ту же учебную игру двумя способами. Пошаговые функции показывают уровни В1, П1, В2 и П2, а рекурсивная функция обходит то же дерево на глубину, заданную параметром moves_left.
Список next_results хранит результаты всех возможных продолжений. Функция any проверяет существование удачного хода, а all — устойчивость стратегии при любом ходе соперника.
Генераторное выражение удобно передавать функции min, когда требуется наименьшее значение. Списочное включение используется в задании 20, где необходимо сохранить два ответа.
Всегда проверяйте конец игры раньше нулевой глубины. Следите за знаком в победном условии, правильно записывайте все команды и исключайте победу на меньшей глубине в заданиях 20 и 21.
Если рекурсивный код перестал быть понятным, вернитесь к пошаговой разметке. На экзамене лучше использовать тот вариант, логику которого вы можете быстро проверить по нескольким ветвям.
В следующей статье перенесём оба варианта программы на игры с двумя кучами.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
