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


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

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

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

Решение.

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

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

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

 

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