Задача 3.
На шашечной доске размера n x n её верхний правый угол имеет номер (1,1). В позиции (i,j) стоит фишка, которая может двигаться по правилу, показанному на рисунке (допустимые ходы обозначены х, шашка - О). Фишка не может дважды ставиться на одно и то же поле.
Играют двое, по очереди двигая фишку. Выигрывает поставивший фишку в позицию (1,1).
Для введённых i,j определить, может ли выиграть первый игрок при наилучших ходах второго.
Написать программу, где первый игрок - компьютер.
|
Решение задачи 3.
Позиция (1,1) проигрышная для игрока, который должен с нее сделать свой очередной ход (фишка уже стоит в позиции (1,1). Все соседние позиции - (1,2), (2,2), (2,1) - выигрышные для делающего текущий ход (они приводят в выигрышную позицию (1,1). Позиции (3,1),(1,3),(3,3) - также проигрышные (любой ход из них приводит в выигрышную позицию, и игрок, делающий следующий ход, выигрывает).
Анализируя позиции дальше, получаем предположение, что позиции с обеими нечетными координатами являются проигрышными для начинающего, все остальные позиции - выигрышные для него. Это действительно так: из проигрышной позиции с обеими нечетными координатами после любого допустимого хода мы попадаем в позицию, где хотя бы одна из координат четная (выигрышную). Из позиции с хотя бы одной четной координатой мы всегда можем опять попасть в позицию с обеими нечетными координатами (проигрышную для делающего очередной ход). Так как последняя позиция (1,1) имеет обе нечетные координаты, то человек, начинающий с позиции, где хотя бы одна из координат четная, всегда сможет сделать так, чтобы после любого его хода фишка была в позиции с обеими нечетными координатами, а в конце концов - в позиции (1,1).
Итак, если i и j нечетные, то первый игрок при наилучших ходах второго всегда проигрывает, иначе - выигрывает.
|
