Каранаев Линар Минтимерович Стерлибашево 2017 содержание глава реферативное изложение
жүктеу/скачать 1.78 Mb.
|
| Задача «Игра Score»
Постановка задачи. Score – это настольная игра для двух игроков, которые двигают на доске одну и ту же фишку с одной позиции на другую. Доска имеет М позиций, пронумерованных от 1 до N, и множество дуг, ведущих от одной позиции к другой.Каждая позиция принадлежит первому или второму игроку, которого мы назовем владельцем этой позиции. Кроме того, каждая позиция имеет положительную цену, причем все цены различны. Позиция 1 – начальная. В начале игры оба игрока имеют счет 0. Игра проводится по следующим правилам. Обозначим С позицию, в которой находится фишка в начале хода. В начале игры позиция С – это 1. Шаг игры состоит из следующих операций. 1. Если величина С больше, чем текущий счет владельца С, то величина Сстановится новым счетом владельца С. Иначе счет владельца С остаетсятем же. Счет другого игрока не изменяется в любом случае. 2. Владелец С выбирает одну из дуг из текущей позиции фишки, и окончание этой дуги задает новую текущую позицию фишки. Заметим, что игрок может сделать несколько последовательных ходов. Игра завершается после того, как фишка возвратится в исходную позицию. Побеждает игрок, имеющий в конце игры больший счет. Дуги всегда организованы так, что выполняются следующие условия: из любой текущей позиции имеется хотя бы одна дуга; каждая позиция Р достижима из стартовой позиции, то есть существуетпоследовательность дуг от стартовой позиции к позиции Р; гарантировано завершение игры через конечное число ходов. Напишите программу, которая играет в эту игру и побеждает. Все позиции, которые предъявляются вашей программе, таковы, что победа возможна вне зависимости от того, делаете ли вы первый ход. Программа противника играет оптимально, и это дает ей шанс выиграть игру у вашей программы. жүктеу/скачать 1.78 Mb. Достарыңызбен бөлісу:
|