ЕГЭ по информатике: Теория игр — две кучи и программное решение

Во многих вариантах ЕГЭ по информатике задания 19–21 строятся на игре с двумя кучами камней: игрок добавляет камни в одну из куч или умножает одну из них, а игра заканчивается, когда суммарное количество камней достигает порога. Ручная таблица позиций здесь становится двумерной, поэтому на экзамене, который целиком проходит на компьютере, многие решают такие задания короткой рекурсивной программой. Материал тренирует оба подхода и основан на элементах кодификатора 2026 года: 2.15 (дискретные игры, выигрышные стратегии), 3.7 (рекурсия) и 3.16 (динамическое программирование с сохранением промежуточных результатов).

Первая часть вопросов — ручной анализ игры с двумя кучами: при каких S Петя выигрывает первым ходом, почему классическое задание 19 для двух куч часто не имеет решений и как решается вариант «Ваня выиграл первым ходом после неудачного хода Пети», какие значения дают задания 20 и 21 и каким ходом Петя переводит игру в проигрышную для Вани позицию.

Вторая часть — чтение и отладка типового кода на Python. Функция f(a, s, m) с параметром числа оставшихся ходов, условие окончания игры с проверкой чётности, any на ходе игрока, для которого ищется стратегия, и all на ходе соперника, декоратор lru_cache. Вопросы требуют предсказать вывод программы, выбрать вызов, решающий задание 21, понять последствия перестановки any и all и изменить решение для варианта с неудачным ходом. Все ответы получены запуском приведённого кода и сверены с перебором позиций.

Письменная работа содержит задания «напишите программу» для новой игры с двумя кучами, обоснование стратегии Пети и объяснение логики any и all; устный экзамен предлагает решить игру вручную, записать решение на Python и найти ошибку в чужом коде. Карточки повторяют связь между вызовами функции и формулировками заданий 19, 20 и 21.

Главная цель — перенести ручной анализ на игру с двумя кучами и научиться писать и проверять рекурсивную программу, которая сразу даёт ответы заданий 19, 20 и 21. Разбор типичных ошибок в программе (например, перепутанная чётность хода, из-за которой «любой ход» и «хотя бы один ход» меняются местами) помогает не потерять баллы из-за одной строки кода. Порядок работы с материалом такой: сначала пройдите тест и прочитайте объяснения к ошибкам, затем повторите карточки, после этого выполните письменную работу, сверяясь с ключевыми пунктами, и в конце проверьте себя на устном экзамене, где задачи нужно решать без подсказок и объяснять ход рассуждения.

  • Анализировать игру с двумя кучами камней и находить ответы на задания 19–21
  • Решать вариант задания 19 с неудачным ходом Пети
  • Записывать рекурсивное решение игры на Python с any, all и lru_cache
  • Выбирать вызов функции для каждого из заданий 19, 20, 21
  • Находить ошибки в программном решении игры

Кодификатор ЕГЭ 2026 по информатике: 2.15 — дискретные игры двух игроков с полной информацией, выигрышные стратегии; 3.7 — рекурсия; 3.16 — динамическое программирование. Спецификация 2026: задания 19, 20, 21.

Пример вопроса

Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза. Игра завершается, когда суммарное количество камней в двух кучах становится не менее 45. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 5 камней, во второй — S камней, 1 ≤ S ≤ 39. Найдите два значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Показать ответ

17 и 19

При S = 17 Петя удваивает первую кучу: (10, 17). Ваня может получить (11, 17), (20, 17), (10, 18) или (10, 34), и из каждой позиции Петя выигрывает (11 + 34 = 45, 20 + 34 = 54, 10 + 36 = 46, 20 + 34 = 54). При S = 19 Петя добавляет камень в первую кучу: (6, 19); ответы Вани (7, 19), (12, 19), (6, 20), (6, 38) позволяют Пете выиграть удвоением второй кучи или добавлением камня (7 + 38 = 45, 12 + 38 = 50, 6 + 40 = 46, 6 + 39 = 45). При S = 16 и S = 18 такого хода нет — это позиции задания 21.

← Информатика

↑ ЕГЭ