ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexey Burdin                        2:5012/32.768  11 Nov 2002  04:08:05
 To : Alex Sadovsky
 Subject : Палочки
 -------------------------------------------------------------------------------- 
 

 > From: /Unknown/
 
 Как после вчерашнего, Alex ?
 
  AS> Думаю, всем известна игpа: на столе лежат 20 одинаковых палочек. За
  AS> один ход игpок может взять одну, две или тpи палочки. Пpоигpывает тот,
  AS> кто забиpает последнюю палочку.
 
     Hу довольно стандартный подход: представить всё это дело как состояния
     (стола с палочками) в граф. ПотОм раскрасить все вершины графа так, что
     + Если состояние стола представлено "белой" вершиной графа, то существует
     ход, приводящий к "белой" вершине при любом ходе соперника. Также "белой"
     вершиной является выигрышная позиция (пустой стол)
     + "Черной" вершиной являются все такие позиции, в которых при любом вашем
     ходе существует ход противника, позволяющий предоставить вам "чёрную"
     позицию. (возможно, также "чёрной" является заведомо проигрышная позиция,
     если таковая имеется)
 
     Применительно сюда:
     0 палочек ДД белая позиция
     1 палочка ДД черная позиция
     2 палочки ДД белая позиция (взять 1 палочку)
     3 палочки ДД белая (вз 2)
     4 б (3)
     5 ч (при ходе 1 ответ 3, 2 ДД 2, 3 - 1)
     6 б (1)
     ...
     9 ч (... см. выше)
     ...
     4n+1 - ч, остальные - б.
 
  AS> Hе подскажете ли алгоpитм беспpоигpышной игpы?
 
     20 палочек ДД белая позиция.
     Hадо брать палочки так, чтобы их оставалось на столе 4n+1.
     Это алгоритм 1-го игрока. При правильных действиях первого игрока у
     второго шансов на победу нет. (симметричность задачи)
     Этот же алгоритм может быть выигрышным для второго игрока, если на
     каком-то ходе ошибся первый игрок.
 
                 Всего хорошего. Alexey.
 ... А что подyмал кpолик, никто не yзнал,
 --- потомy что кpолик был очень воспитанный.
  * Origin: Megabyte (2:5012/32.768)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Палочки   Alex Sadovsky   06 Nov 2002 00:48:23   Re: Палочки   Andrew Ezhguroff   06 Nov 2002 05:58:28   Палочки   Nickita A Startcev   06 Nov 2002 06:54:58   Re: Палочки   Andrew Starsh   06 Nov 2002 09:10:59   Re: Палочки   Igor Bury   06 Nov 2002 09:24:51   Палочки   Egor Tsygvintsev   06 Nov 2002 22:00:38   Палочки   Dmitry Shram   07 Nov 2002 01:05:44   Re: Палочки   Sergey Bychkov   09 Nov 2002 01:14:58   Палочки   Alexey Burdin   11 Nov 2002 04:08:05