СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 26 № 11651

Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (3, −5). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y) в одну из трёх точек: или в точку с координатами (x + 3, y), или в точку с координатами (x, y + 4), или в точку с координатами (x, y + 5). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0, 0) больше 9 единиц. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Постройте дерево партии для выигрышной стратегии (в виде рисунка или таблицы).

Решение.

Квадрат расстояния от фишки до точки с координатами (0, 0): r2 = x2 + y2. Побеждает игрок, после хода которого r2 > 81. Алгоритм выигрышной стратегии определим при помощи дерева всех возможных партий. Не будем приводить здесь полное дерево, отметим лишь, что при любом ходе первого игрока второй игрок имеет выигрышный набор ходов.

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

Дерево содержит все возможные варианты ходов первого игрока. Из него видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.

 

Источник: Информатика. Ти­по­вые те­сто­вые за­да­ния. В. Р. Лещинер. 2017. Вариант 4.