Задачи 19–21 из ЕГЭ по информатике — одни из самых интересных и логически насыщенных. Они относятся к разделу «Теория игр» и проверяют умение анализировать стратегии двух игроков в простой математической игре. В этой статье мы разберём универсальный метод решения, основанный на рекурсивном переборе с ограничением глубины ходов — именно так, как это делается в вашем конспекте.
Решение кодом на Python
🔹 Основные правила игры
- Есть куча камней, изначально в ней S камней (1 ≤ S ≤ 38).
- Два игрока: Петя (ходит первым) и Ваня.
- За один ход можно:добавить 1 камень,
добавить 3 камня,
умножить количество камней на 2. - Игра завершается, когда в куче становится ≥ 39 камней.
- Побеждает тот, кто сделал последний ход (т.е. довёл кучу до 39 или более).
Аналогично рассматривается и обратный тип задачи, где:
- начальное S ≥ 20,
- возможные ходы: −2, −5, //3 (целочисленное деление),
- игра заканчивается при ≤ 19 камнях,
- побеждает сделавший последний ход.
🔹 Теоретическая основа: рекурсивная функция с глубиной
Ключевой инструмент — функция F(s, m), где:
- s — текущее количество камней,
- m — оставшееся число полных ходов (пара «ход Пети + ход Вани» считается за 2 уровня).
Функция возвращает True, если текущий игрок может выиграть при оптимальной игре.
Базовые условия:
- Если игра уже завершена (s >= 39 в первой версии или s <= 19 во второй), то:победил тот, чей ход был последним → проверяем чётность m.
- Если m == 0 — ходы закончились, текущий игрок не может выиграть → возвращаем False.
Рекурсивный переход:
Для каждого возможного хода строим список результатов:
- Если сейчас ходит Петя (m % 2 == 0), он хочет выиграть → используем any(h).
- Если сейчас ходит Ваня (m % 2 == 1), и мы анализируем гарантированную победу Пети, то Ваня будет мешать → используем all(h).
Это отражает суть стратегии: первый игрок стремится к победе хотя бы одним путём, второй — мешает любыми способами.
🔹 Задача 19: когда Петя проигрывает за один ход, но Ваня выигрывает своим первым
Нужно найти минимальное S, при котором:
- Петя не может выиграть за один ход → F(S, 1) == False,
- Но при любом его ходе Ваня выигрывает сразу → F(S, 2) == True.
В коде это:
Результат: S = 19 (для задачи №17638).
🔹 Задача 20: у Пети есть выигрышная стратегия вторым ходом
Условия:
- Петя не выигрывает первым ходом → F(S, 1) == False,
- Но всегда выигрывает вторым, независимо от ходов Вани → F(S, 3) == True.
Код:
Ответ: 16, 18.
🔹 Задача 21: у Вани есть шанс выиграть — первым или вторым ходом
Ищем минимальное S, при котором:
- Ваня может выиграть (первым или вторым ходом),
- Но не может гарантированно выиграть первым ходом.
Это значит:
- Петя не выигрывает за два хода → F(S, 2) == False,
- Но Ваня имеет стратегию на 4 хода → F(S, 4) == True.
Код:
Ответ: 15, 17 → минимальное 15.
💡 Почему это работает?
Метод моделирует дерево игры до нужной глубины. Чётность m определяет, чья сейчас очередь, а логика any/all отражает цели игроков:
- any — "найдётся хотя бы один выигрышный путь",
- all — "противник не сможет помешать ни при каком ответе".
Этот подход универсален: он работает и для игр с увеличением, и с уменьшением кучи — достаточно изменить условия завершения и возможные ходы.
Полный код решения:
✅ Заключение
Освоив этот алгоритм, вы сможете решать любые задачи 19–21 из ЕГЭ по информатике — даже если правила игры немного изменятся. Главное — правильно задать:
- Условие окончания игры,
- Возможные ходы,
- Логику any/all в зависимости от очерёдности.
Подпишитесь на мой канал и научитесь решать все задания ЕГЭ по информатике!
Удачи на экзамене!
Записаться ко мне на занятия можно тут https://vk.com/nebolsink