← Вернуться к оглавлению
Alterna · глава 25 · страница 25.5

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

Генератор случайных вариантов по теории игр с автопроверкой. Каждый раз новое условие.

Два игрока ходят по очереди, применяя разрешённые операции к числу. Кто первым достигает граничного значения — выигрывает. Задача: найти выигрышные и проигрышные начальные позиции.

ФГОС ЕГЭ №19 ЕГЭ №20 ЕГЭ №21
01

Настройки варианта

⚙️Параметры игры
03

Как решать?

Алгоритм нахождения проигрышных позиций:

  1. Позиции ≥ N (граничные) — выигрышные (ты уже выиграл).
  2. Позиция проигрышная, если все ходы из неё ведут в выигрышную позицию.
  3. Позиция выигрышная, если хотя бы один ход ведёт в проигрышную позицию.
  4. Заполняем таблицу от N−1 вниз (или от 1 вверх для убывающих игр).

Что спрашивают:

  • Задание 19 — максимальная проигрышная позиция (второй выигрывает при оптимальной игре).
  • Задание 20 — все начальные позиции в диапазоне [a, b], с которых второй игрок выигрывает.
  • Задание 21 — максимальная позиция в диапазоне [a, b], с которой первый игрок выигрывает.
04

BST-конструктор

Вводи ключи — строй дерево, смотри обходы, удаляй узлы.

🌳BST Constructor
Дерево пусто — вставь первый ключ
Как работает BST:
• Корень — первый вставленный ключ.
• Меньший ключ — в левое поддерево, больший — в правое.
• Inorder обход даёт отсортированную последовательность!
• Удаление узла с двумя детьми: заменяем минимумом правого поддерева.