Когда интуиции лучше промолчать

В  жизни нам часто доводится принимать решения в ситуациях,
когда возможных вариантов поведения несколько, и каждый из них мо-
жет вызвать различные, иногда трудно предсказуемые последствия. В
самом простом случае такая ситуация возникает при игре двух лиц,
каждый из которых хочет выиграть и делает для этого все, что в его
силах. Разумеется, при принятии очередного хода всегда можно поло-
житься на свою интуицию (что зачастую впоследствии приводит к се-
тованию: «Интуиция опять промолчала»). Но можно попробовать проа-
нализировать игру и попытаться принять решение, основываясь на об-
наруженных закономерностях. Правда, иногда для этого приходится
выполнять достаточно много вычислений — но на это у нас и есть
компьютер. Особенно он полезен при анализе игр с полной информаци-
ей. Это такой вид игр, в которых для каждой из ситуаций, которые
могут возникнуть в ходе игры, заранее известны все возможные ходы,
которые могут сделать игроки.
Рассмотрим несколько таких игровых задач, которые встречались
на олимпиадах разного уровня.
2Задача 1. 1 (Республиканская олимпиада 1993 года.)
1Есть две обезьяны и куча из L бананов. Обезьяны по очереди,
1начиная с первой, берут из кучи бананы, причем 1-ая обезьяна может
1при каждом очередном ходе взять из кучи либо a 41 1, либо a 42 1,…, либо
1a 4S 1 бананов (а 41 11, m>1. Два игрока ходят по очереди.
1Ход состоит в следующем: игрок зачеркивает два пустых стоящих ря-
1дом (по горизонтали или по вертикали) квадрата. Проигрывает тот,
1кто не может сделать очередного хода. 0
1Кто выигрывает в этой игре?
Вне зависимости от величин n и m всегда выигрывает второй иг-
рок! Ему достаточно все время делать ход, симметричный ходу перво-
го игрока относительно центра доски.
А что будет при n и m разной четности, или когда оба этих
числа нечетны?
Попытайтесь решить следующие игровые задачи. Если не удастся,
то в конце статьи — подсказки.
2Задача 3. 1 На шашечной доске размера n x n ее верхний правый
1угол имеет номер (1,1). В позиции (i,j) стоит фишка, которая мо-
1жет двигаться по правилу,показанному на рисунке (допустимые ходы
1обозначены х, шашка — О). Фишка не может дважды ставиться на одно
1и то же поле. Играют двое, по очереди двигая фишку. Выигрывает
1поставивший фишку в позицию (1,1).
1Для введённых i,j определить, может ли выиграть первый игрок
1при наилучших ходах второго.
1Написать программу, где первый игрок- компьютер.
n 1
?????????????????????????????????????
? ? ? ? ? ? ? ? ? ? 1
?????????????????????????????????????
? ? ? ? ? ? ? ? ? ?
?????????????????????????????????????
? ? ? x ? x ? x ? ? ? ? ?
?????????????????????????????????????
? ? ? ? O ? x ? ? ? ? ?
?????????????????????????????????????
? ? ? ? ? x ? ? ? ? ?
?????????????????????????????????????
? ? ? ? ? ? ? ? ? ? n
?????????????????????????????????????
2Задача 4. 1На линейке из m клеток в разных концах стоят две
1фишки, 0 1которые ходят по очереди. Каждая из фишек может ходить вле-
1во или вправо не более чем на К клеток (m<=80; К<=m-2). При этом 1нельзя перешагивать через фишку и нельзя оставаться на месте. Фиш- 1ка проигрывает, если она не может сделать ход. Написать программу, 1реализующую выигрышную стратегию для одной из фишек. При этом раз- 1решается передача хода в самом начале игры. Предусмотреть контроль 1входных данных. 0 2Задача 5. 1Задаются натуральные числа N и K, N<=K. Двое играю- 1щих называют по очереди числа, меньшие K+1, по следующим правилам. 1Начинаем с числа N. Каждый новый ход должен увеличивать одну из 1цифр предыдущего числа на 1, 2 или 3. Проигравшим считается тот, 1кто называет число K. Для заданных N и K необходимо определить, 1может ли выиграть игрок, делающий первый ход, при наилучших после- 1дующих ходах противника. Вывести сообщения «Первый выигрывает» или 1″Первый проигрывает». В случае возможности выигрыша первым игро- 1ком, требуется напечатать все его возможные первые ходы. 0 1Пример. N=996, K=999. 1Вывод: Первый выигрывает. Выигрышный ход(ы): 998 2Задача 6. 1 Вводится целое число K>=1. Бумажная полоса разбита
1на N клеток (K<=N<=40). Играют двое, по очереди выбирая и зачерки- 1вая K пустых смежных клетки. Выигрывает сделавший последний ход. 1 2 N ????????????????????? ?????????? ? ? ? ? ? . . . ? ? ????????????????????? ?????????? 1Требуется: 11) Для введенного N определить, имеет ли игрок 1 выигрышную 1стратегию ( т.е. может ли игрок 1 выиграть при наилучших последую- 1щих ходах игрока 2). Выдать сообщение вида ‘У игрока 1 (не) су- 1ществует выигрышная стратегия’. 0 12) Для введенного N и заданного первого хода определить, име- 1ет ли игрок 1 выигрышную стратегию. 13) Провести игру для введенного N и первого хода игрока 1. За 1второго игрока играет программа. Ходы первого вводятся с клавиату- 1ры. Цель второго игрока — победа. Ход задается индекcoм ячейки L 1(1<=L<=N-K+1).При этом вычеркиваются клетки с индексами от L до 1L+K-1. После каждого хода выводится текущее игры в виде 1 2 3 … N * * 1Сверху печатается номер позиции. Зачеркнутые клетки помечают- 1ся символом ‘*’. В конце игры выдать сообщение ‘Победа игрока 11(2)’. 0 2Подсказки. Задача 3. Позиция (1,1) проигрышная для игрока, который дол- жен с нее сделать свой очередной ход (фишка уже стоит в позиции (1,1). Все соседние позиции — (1,2), (2,2), (2,1) — выигрышные для делающего текущий ход (они приводят в выигрышную позицию (1,1). Позиции (3,1),(1,3),(3,3) — также проигрышные (любой ход из них приводит в выигрышную позицию, и игрок, делающий следующий ход, выигрывает). Анализируя позиции дальше, получаем предположение, что пози- ции с обеими нечетными координатами являются проигрышными для на- чинающего, все остальные позиции — выигрышные для него. Докажите это предположение. Задача 4. Предположим, что левая фишка (будем называть ее Ф1) можем ходить только вправо, а правая фишка Ф2 — только влево, и ход передавать нельзя. Решение задачи в первоначальной постановке сводится к решению задачи при налагаемых выше ограничениях. Пусть первый ход делает Ф1. Ф1 выигрывает, если количество клеток между фишками d(Ф1,Ф2) (вначале равное m-2) не делится на- цело на k+1. Действительно, пусть Ф1 делает такой ход, что d(Ф1,Ф2) кратно k+1. Какой бы ход не сделала Ф2 (например, на L клеток влево), Ф1 следующим ходом смещается на k+1-L клеток впра- во, и, таким образом, после хода Ф1 расстояние d(Ф1,Ф2) снова кратно k+1. А так как 0 также делится на k+1 нацело, то наступит момент, когда d(Ф1,Ф2)=0 и предыдущий ход был ходом Ф1, т.е. Ф2 проиграла. Если (m-2) mod (k+1)=0, то Ф1 при наилучших ходах Ф2 проигрывает. Если разрешить фишкам ходить как влево, так и вправо, то всегда выигрывает та фишка, после хода которой d(Ф1,Ф2) кратно k+1. Задачи 5 и 6. Идея решения аналогична предложенной для задачи 1. И.А.Волков

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

методические материалы по информатике