Начал решать на эту тему, вот легкая задача http://acm.timus.ru/problem.aspx?space=1&num=1465 вроде бы нужно составить функцию Шпрага-Грандии просто составить для нее последовательность значений по формуле g[n] = {mex} ( g[n-2], g{i-2}^g{n-1-i}) но я не знаю с чего начать, т.е как рекурсивно составить последовательность?
вот есть статья на эту тему http://e-maxx.ru/algo/sprague_grundy
если кто-нибудь знает как решаются такие задачи помогите разобраться пожалуста
Кто Вам подсказал формулу именно в таком виде?
Просто если дойти до нее самостоятельно, то база рекуррентного соотношения (g[0] и g[1]) ну просто совсем очевидна.
формулу нашел по ссылке которая снизу,вот,думаю что g[0]=0,g[1]=1,все равно не совсем понимаю
Проследим, что происходит, когда одна пешка сделает ход вперёд. Следующим ходом противник будет обязан съесть её, затем мы будем обязаны съесть пешку противника, затем снова он съест, и, наконец, наша пешка съест вражескую пешку и останется, "упёршись" в пешку противника. Таким образом, если мы в самом начале пошли пешкой в колонке 1 < i < n, то в результате три колонки [i-1; i+1] доски фактически уничтожатся, и мы перейдём к сумме игр размера i-2 и n — i — 1. Граничные случаи i=1 и i=n приводят нас просто к доске размера n-2.
Зачем копипастить-то? Я уже туда зашел и все прочитал.
Думаете-то Вы правильно, но было бы интересно посмотреть на Ваши рассуждения.
У меня за час так и не получилось придумать объяснение, которое Вы сможете понять. Я сдаюсь.
Я пытался придумать какую-то конкретную интерпретацию для функции Шпрага-Гранди, но сделать это у меня не получилось. А оперировать абстрактными понятиями Вы, судя по Вашим комментариям, пока не умеете. Получается, что для того, чтобы объяснить Вам теорию Шпрага-Гранди, нужно сначала научить Вас абстрактному мышлению, а я даже не помню, как научился ему сам...
Видимо, Вам стоит до поры до времени отложить эту тему.
Все равно спасибо
Да, действительно,функция Шпрага-Гранди довольно сложна для понимания не то чтобы для серого на кф, а даже и для фиолетовых. Поэтому отложите ее до лучших времен, порешайте задачи на реализацию если Вы серый.
У нас в команде вообще никто не осиливал эту штуку... Вообще лучше общий уровень интеллекта качать. Дефолтный умный человек без знания всяких специфических алгоритмов сейчас без проблем станет фиолетовым (см. RodionGork например)
Согласен с Вами, я сам максимум что знаю — дерево отрезков и Дейкстру.
шта?
Ты все-таки ее знал? Окай
Что там понимать-то? ШГ чем-то отличается от "делай вот так и будет решение"? Вводим функцию, конструктивно показываем способ победы за обе стороны, после этого доказываем, что для прямой суммы игр значение получается по ним-сумме (т.е. ксором). Кто-то знает что-то лучше для ШГ?
Учи невыучиваемому
Для понимания, надо ввести несколько понятий позиции в игре в ниме это конкретный набор кучек. Допустим у нас две кучки 3 и 2 камня. Вот первая позиция обозначим ее (3,2), другие позиции этой игры (3,1),(3,0),(2,1) и тд (0,0). Ход в игре переход из одной позиции в другую например взяли два камня из первой кучи Значит ход (3,2)->(1,2). Терминальная позиция эта позиция из которой нет хода т.е. в примере (0,0). Опции позиции это все возможные позиции куда можно попасть за один ход например для (2,1) опции {(1,1),(0,1),(2,0)} Позиции (0,0) и (1,1) не являются опциями для (2,1), в них за один ход по правилам нима попасть нельзя. Теперь функция Шпрага-Гранди (Ш-Г) строится рекурсивно для терминальной она равна 0, а дальше как mex по опциям. Надо правда понять, что а правили игры после хода разбиваются на суммы игр, т.е и для суммы функция Ш-Г вычисляется как ксор по играм. Чтобы в этом разобраться можно рекомендовать лекции Фролова посмотреть и примеры разобрать