Задание 19. Анализ алгоритма логической игры: ЕГЭ по информатике

Задание 19 ЕГЭ по информатике проверяет умение анализировать алгоритм логической игры. Обычно даётся описание игры двух игроков (например, с камнями или кучами), где нужно определить, кто выигрывает при оптимальной игре, или найти выигрышную стратегию, или минимальное/максимальное число ходов.…

Что нужно знать

Задание 19 относится к анализу алгоритмов логических игр, чаще всего с двумя игроками и конечным числом ходов.
В условии всегда оговариваются правила ходов, начальная позиция, условие победы (кто выигрывает) и иногда ограничение на количество ходов.
Требуется определить результат игры при оптимальной игре обоих игроков (обычно выигрывает первый или второй).
Ответом может быть число (например, номер выигрышного хода, количество ходов) или последовательность символов (например, 'ППВ' — первый, второй, выигрыш).
Для решения нужно построить дерево игры или использовать рекурсивную функцию с запоминанием выигрышных/проигрышных позиций.
Позиция называется выигрышной, если существует ход в проигрышную позицию; проигрышной, если все ходы ведут в выигрышные позиции.

Термины и понятия

Логическая игра: игра с полной информацией, где игроки делают ходы по определённым правилам, и результат зависит от их решений.
Выигрышная позиция: позиция, из которой игрок, чей ход, может гарантировать себе победу при любой игре противника.
Проигрышная позиция: позиция, из которой игрок, чей ход, не может выиграть, если противник играет оптимально.
Дерево игры: граф всех возможных позиций и ходов, позволяющий проанализировать исход игры.
Оптимальная игра: стратегия, при которой игрок стремится максимизировать свой результат (выиграть или затянуть игру).
Мемоизация: сохранение результатов вычислений для повторного использования при рекурсивном анализе.
Динамическое программирование: метод решения задач путём разбиения на подзадачи и сохранения результатов.
Ход: изменение состояния игры одним из игроков согласно правилам.

Частые ошибки

Не учитываются все возможные ходы противника, рассматривается только один вариант.
Неправильно определяется условие победы: например, путают, кто должен сделать последний ход.
Неверно интерпретируется оптимальная игра: игрок может не выиграть, а затянуть игру, что влияет на количество ходов.
При построении дерева игры пропускаются некоторые состояния из-за невнимательности.

Как пройти тему

В курсе «Информатика» тема «Задание 19. Анализ алгоритма логической игры» занимает 6 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Начать бесплатно Открыть курс

Другие темы раздела

← Предыдущая тема: Задание 18. Анализ данных с помощью электронных таблиц
Следующая тема: Задание 20. Поиск выигрышной стратегии игры

Все темы: ЕГЭ по информатике