1) Задача
Двое играют в следующую игру:В ряд выстроены N белых камней, за один ход разрешается перекрасить один белый камень в черный, если соседние камни белые, проигрывает тот кто не может совершить ход.
2) Что я делаю?
Пишу рекурсивную функцию подсчета функций Гранди, следующим образом:
если N = 0 то ответ очевидно 0 иначе
если N <= 3 то сопоставляю ним-число 1 (Выигрышная позиция) иначе
создаю пустое множество A
Запускаю цикл i от 1 до N если перекрасить i ый камень то мы придем в состояние из двух независимых игр меньшей размерности i - 2 и n - i - 1, считаю для каждой из них функцию Гранди и добавляю в множество A исключающее или двух полученных значений функции, обрабатывая граничные случаи.
Нахожу из данного множества минимальное неотрицательное число не встречающееся в нем. Возвращаю ответ.
3) Некоторые тесты
4 проигрышная позиция (ок)
5,6,7 выигрышная позиция (ок)
8 проигрышная позиция (на что моя программа возвращает неверный результат)
4) Что-то я делаю не правильно. Подскажите как можно свести эту игру к ним-игре и/или подскажите ошибку в моих рассуждениях. Спасибо.
4) Что-то я делаю не правильно. Подскажите как можно свести эту игру к ним-игре и/или подскажите ошибку в моих рассуждениях. Спасибо.
Да можно
Edit: впрочем, можно даже с N = 0 начать, вообще без базы. Минимальное неотрицательное число, не встречающееся в пустом множестве, равно нулю.
Не хочется создавать пост ради одного вопроса, поэтому бампаю этот. Итак, мы посчитали функцию Гранди для всех состояний игры и мы можем отвечать для каждого состояния, является ли оно проигрышным или выигрышным при оптимальной игре обеих сторон. А возможно ли, зная значения Гранди, восстановить процесс оптимальной игры? Т.е. какие именно ходы должны совершать игроки.
Позиция выигрышная, если функция Гранди не равна 0, иначе проигрышная.
Смотрим на наше состояние и перебираем ходы. Если наше состояние выигрышное, то из него можно пойти в проигрышное(у которого функция равна 0). Такой ход и будет оптимальным. Если состояние проигрышное, то все-равно проиграем, поэтому можно как угодно ходить :)
Ок, спасибо)