Есть игра "Три числа" - на листке бумаги написано 3 числа, не отрицательных, большых от нуля или равных ему.
Тот, у кого есть ход, вычеркивает ОДНО из этих чисел и на его место ставит меньшее, но НЕ МЕНЬШЕ НУЛЯ. НУЛЬ НЕЛЬЗЯ ВЫЧЕРКИВАТЬ. Игра заканчивается, когда не возможно ничего сделать, выигрывает тот, который сделал последний ход. Как, зная все 3 числа и того, кто ходит первым, определить, кто выиграет (то есть какая стратегия и тактика этой игры)?
ПОДСКАЗКИ:
1) при числах 3, 4, 5 выигрывает тот, кто ходит первый;
2) при числах 7,0,7 выигрывает второй, он должен повторять ходы противника
Просьба помочь мне, а именно - подсказать тактику/стратегию этой игры
http://ru.wikipedia.org/wiki/%D0%9D%D0%B8%D0%BC_%28%D0%B8%D0%B3%D1%80%D0%B0%29
И дальше - гуглом ищешь более подробное объяснение, если нужно.
Большущее спасибо...
Возник вопрос - а как к этому можно додуматься самостоятельно, если ничего об этом ранее не знал?
А ведь задача-то с школьной олимпиады - задание следующее: определить по трем числам победителя и вывести общий счет первого и второго игрока
Ну, как-то можно Меня тоже такой вопрос интересует иногда, только для других задач И кстати в свое время и для этой тоже - сам не придумал. Действительно, очень уж специфично, на первый взгляд.
А на самом деле, этот алгоритм лежит в основе значительно более крупного объекта в теории игр - чисел Спрага-Грюнди. Хочешь - погугли-почитай.
От школьников никаким образом не может требоваться придумывать такие вещи на школьных олимпиадах; просто именно эта игра - считай, классика теории игр, и такие вещи считаются общеизвестными (да и, начиная с некоторого уровня, такими и являются).
Так что ты столкнулся скорее с проблемой нехватки знаний чем с проблемой нехватки смекалки, не расстраивайся
P.S. Хочешь, подумай над обратной игрой: тот, кто делает последний ход - проигрывает. Вот тут уже можно придумать самому, хотя тоже непросто.
Bokul , ищи обширнее
Кое-что находит об "Спаре-Грюнди" и "Шпраге-Грюнди"
Например: http://mashinnyi-razum.narod.ru/mirovoegospodstvo/mashinny_razum_-_mirovoe_gospodstvo1.html
Ну и статья, которая ставит "все точки над i": http://en.wikipedia.org/wiki/Sprague–Grundy_theorem (в Википедии ТОЛЬКО на английском)
Ну и на иглише можно что-то найти...
В тему: http://en.wikipedia.org/wiki/Category:Combinatorial_game_theory
http://en.wikipedia.org/wiki/Dynamic_programming (на разных языках, но на английском - самая полная версия статья)
Кстати, кстати. Теория - теорией, но такой вопрос: какие были ограничения на числа? Чисел ровно три, и если каждое, скажем, не больше 100, то она решается очень легко без всякой теории (как?)
Относительно недавно на одной польской олимпиаде была задача на очень сложную теорию игр, и после тура организаторы (в высшей степени компетентные люди) рекомендовали вот эту ссылку: http://www.math.ucla.edu/~tom/Game_Theory/Contents.html
Сам не смотрел, но смело рекомендую
Все три числа >=0 и <=1000
Это что-то меняет?
Документ скачал, буду разбиратся (английским владею не свободно), спасибо
Меняет принципиально.
Тогда все решалось проще (конечно, кодить проще классический алгоритм, но придумать его сложнее).
Просто генерим все проигрышные тройки, т.е. такие тройки, в которых игрок, делающий первый ход, проигрывает.
1) Тройка (0, 0, 0) - проигрышная (нельзя сделать ход).
2) Тройка (a, b, c) - проигрышная тогда и только тогда, когда из нее нельзя сделать ход в проигрышную тройку.
Делаешь три вложеных цикла, и проверяешь. Тут, правда, есть свои сложности - с хранением найденных троек, особенно если давали только турбо паскаль (память >64K можно выделить только динамически).
Довольно удобна такая уловка: из второго правила сразу видим, что для данных a и b может быть только одно с такое, что тройка (a, b, c) - проигрышная. Поэтому можно завести двумерный массив 1000х1000, и его значение в точке (a, b) - это соответствующая с, или -1, если с еще не нашли. В таком вот духе
Разобраться стоит и с этим решением, возможно, от вас ждали именно чего-то такого.