Использование рекуррентных соотношений для игровых задач.

Пример #3.
	Двое играют в следующую игру: начиная с некоторой даты (день, месяц) они по очереди называют следующую, причем можно увеличивать либо номер дня, либо номер месяца (одновременное изменение номеров дня и месяца не разрешается). Проигравшим считается тот, кто называет дату 31.12. Какие даты должен выбирать первый игрок, чтобы выиграть?
	При решении такого рода задач строится множество всевозможных позиций игры. В нашей задаче это таблица размера 31´12, каждая клетка которой соответствует некоторой дате, причем не все клетки таблицы доступны (некоторых дат нет в календаре, например 30.02). Для каждой позиции определяется, выигрышная она или проигрышная по следующим правилам. Всегда имеется одна или несколько позиций, когда игра закончена, и для которой заранее известно (по правилам игры), выигрышные они или проигрышные. В нашей задаче это позиция (31,12), которая является проигрышной. Если для позиции еще не известно, выигрышная она или проигрышная, но все ходы из нее ведут только в проигрышные позиции, то она выигрышная. В нашей задаче это позиции (31,10) и (30,12), так как любой ход из них ведет в позицию (31,12), которая является проигрышной. Если для позиции еще не известно, выигрышная она или проигрышная, но есть ход из нее, который ведет в выигрышную позицию, то она проигрышная. В нашей задаче это позиции (1-29,12), так есть ход из них, который ведет в позицию (30,12), которая является выигрышной. Используя правила, необходимо для каждой позиции определить, выигрышная она или проигрышная. После того, как статус позиций определен, стратегия игрока такова. Своим ходом он становится в выигрышную позицию. Любой ход противника приводит того в проигрышную позицию, откуда игрок снова ходит в выигрышную позицию.

Назад