В заданиях 19–21 ЕГЭ по информатике два игрока по очереди меняют кучу камней, а спрашивают, при каком начальном размере кучи у кого из них есть выигрышная стратегия. Руками это дерево ходов в три-четыре уровня глубиной для каждого начального значения. На Python его перебирает одна рекурсивная функция в семь строк, и она отвечает на все три вопроса. Код ниже запускается прямо на странице. Пример задачи составлен для этой статьи, на экзамене ходы и граница будут другими, а код — тот же.
f(29, 2): при любом ходе Пети выигрывает Ваня
all. Когда ходит сам нужный игрок, ему хватит одного удачного хода — any. Из 29 Ваня выигрывает первым ходом, что бы ни сделал Петя.Пример задачи
Два игрока, Петя и Ваня, играют с кучей камней. Ходят по очереди, первым ходит Петя. За один ход можно добавить в кучу один камень, добавить четыре камня или увеличить число камней вдвое. Игра заканчивается, когда в куче становится не менее 60 камней; побеждает тот, кто сделал последний ход. В начале в куче S камней, 1 ≤ S ≤ 59.
- Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Найди минимальное S, при котором так могло быть.
- Найди два наименьших S, при которых Петя не может выиграть первым ходом, но выигрывает вторым ходом при любой игре Вани.
- Найди минимальное S, при котором у Вани есть стратегия выиграть первым или вторым ходом при любой игре Пети, но нет стратегии гарантированно выиграть первым ходом.
Функция, которая отвечает на все вопросы
def f(s, m):
if s >= 60:
return m % 2 == 0
if m == 0:
return False
h = [f(s + 1, m - 1), f(s + 4, m - 1), f(s * 2, m - 1)]
return any(h) if m % 2 != 0 else all(h)
print(f(30, 1), f(29, 2), f(28, 2))True True Falses— сколько камней в куче.m— каким по счёту ходом должен выиграть нужный игрок: 1 — первый ход Пети, 2 — первый ход Вани, 3 — второй ход Пети, 4 — второй ход Вани.- Если в куче уже не меньше 60, игра окончена, и
m % 2 == 0отвечает, сделал ли последний ход нужный игрок. - Если ходов не осталось (
m == 0), а куча не набралась, нужный игрок не успел выиграть. h— ответы для трёх возможных ходов: +1, +4 и ×2. На экзамене сюда подставь ходы из своего условия.- Когда ходит нужный игрок (
mнечётное), ему хватит одного удачного хода —any. Когда ходит соперник (mчётное), выигрыш должен получиться при любом его ходе —all.
Проверка на трёх позициях. f(30, 1) — True: Петя удвоит кучу до 60 и выиграет первым ходом. f(29, 2) — True: это схема выше, из 29 любой ход Пети даёт Ване победу. f(28, 2) — False: из 28 Петя может положить один камень, и из 29 Ваня одним ходом не выиграет.
Задания 20 и 21
def f(s, m):
if s >= 60:
return m % 2 == 0
if m == 0:
return False
h = [f(s + 1, m - 1), f(s + 4, m - 1), f(s * 2, m - 1)]
return any(h) if m % 2 != 0 else all(h)
print("20:", [s for s in range(1, 60) if not f(s, 1) and f(s, 3)])
print("21:", [s for s in range(1, 60) if not f(s, 2) and f(s, 4)])20: [25, 28]
21: [24, 27]- Задание 20: «Петя не может выиграть первым ходом» —
not f(s, 1), «выигрывает вторым ходом при любой игре Вани» —f(s, 3). Подходят 25 и 28 — это и есть два наименьших значения. - Задание 21: «нет стратегии выиграть первым ходом» —
not f(s, 2), «выигрывает первым или вторым ходом» —f(s, 4). Минимальное значение — 24.
Задание 19: неудачный ход Пети
В задании 19 Петя играет не лучшим образом: его ход «неудачный», то есть хотя бы один из ходов Пети даёт Ване выигрыш. Значит, перебирать нужно через any на каждом уровне, и для этого задания пишут отдельную функцию:
def f19(s, m):
if s >= 60:
return m % 2 == 0
if m == 0:
return False
h = [f19(s + 1, m - 1), f19(s + 4, m - 1), f19(s * 2, m - 1)]
return any(h)
print("19:", min(s for s in range(1, 60) if f19(s, 2)))19: 15При 15 камнях Петя может удвоить кучу до 30, и тогда Ваня тоже удвоит её до 60. Ответы к примеру: 19 — 15, 20 — 25 и 28, 21 — 24.
Частые ошибки
Задание 19 через all. Если взять для него общую функцию, получится другой ответ:
def f(s, m):
if s >= 60:
return m % 2 == 0
if m == 0:
return False
h = [f(s + 1, m - 1), f(s + 4, m - 1), f(s * 2, m - 1)]
return any(h) if m % 2 != 0 else all(h)
print("19 через all:", min(s for s in range(1, 60) if f(s, 2)))19 через all: 2929 — это наименьшая куча, из которой Ваня выигрывает при любом ходе Пети, а в задании 19 речь о неудачном ходе, то есть хватает одного.
Граница игры. «Не менее 60» — это s >= 60, а «более 60» — уже s > 60, и ответы сдвигаются все сразу: с s > 60 в этом примере задание 19 дало бы 16, а 21 — 25. Сверяй знак с условием до запуска.
Задание 2 о таблицах истинности разобрано в статье «Задание 2 ЕГЭ на Python», задание 6 с черепахой — в статье «Задание 6 ЕГЭ на Python», а какие ещё задания решают программой — в статье «Python для ЕГЭ по информатике». Свой вариант игры удобно отлаживать в песочнице Python: там есть пошаговое выполнение, и видно, как рекурсия спускается по дереву ходов.