ЕГЭ 19–21: теория игр

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 25 · страница 25.5
ЕГЭ 19–21: теория игр
Генератор случайных вариантов по теории игр с автопроверкой. Каждый раз новое условие.
Два игрока ходят по очереди, применяя разрешённые операции к числу. Кто первым достигает граничного значения —
выигрывает
. Задача: найти выигрышные и проигрышные начальные позиции.
ФГОС
ЕГЭ №19
ЕГЭ №20
ЕГЭ №21
01
Настройки варианта
⚙️
Параметры игры
Тип операций
Граничное значение N
02
Условие задачи
📊
Таблица позиций
Выигрышная (В) — первый ходит, он выигрывает
Проигрышная (П) — первый ходит, он проигрывает
Граница N — выигрыш автоматически
Нажми на ячейку, чтобы увидеть объяснение.
0/3
правильных ответов в этом варианте
03
Как решать?
Алгоритм нахождения проигрышных позиций:
Позиции
≥ N
(граничные) —
выигрышные
(ты уже выиграл).
Позиция
проигрышная
, если
все
ходы из неё ведут в выигрышную позицию.
Позиция
выигрышная
, если
хотя бы один
ход ведёт в проигрышную позицию.
Заполняем таблицу от N−1 вниз (или от 1 вверх для убывающих игр).
Что спрашивают:
Задание 19
— максимальная проигрышная позиция (второй выигрывает при оптимальной игре).
Задание 20
— все начальные позиции в диапазоне [a, b], с которых
второй
игрок выигрывает.
Задание 21
— максимальная позиция в диапазоне [a, b], с которой
первый
игрок выигрывает.
04
BST-конструктор
Вводи ключи — строй дерево, смотри обходы, удаляй узлы.
🌳
BST Constructor
Ключ
Дерево пусто — вставь первый ключ
Как работает BST:
• Корень — первый вставленный ключ.
• Меньший ключ — в левое поддерево, больший — в правое.
• Inorder обход даёт отсортированную последовательность!
• Удаление узла с двумя детьми: заменяем минимумом правого поддерева.