WoW 3: Идем к ним?

Задача Идем к ним?
«У крота и землеройки имеется [latex]n[/latex] зёрен чего-то вкусного. Они по очереди съедают любое количество зерен, но не более половины оставшегося количества. Можно съедать только целое число зёрен. Если игрок не может сделать очередной ход, то он считается проигравшим и ему приходится бежать в магазин за следующей порцией вкусных зёрен. На каждом шаге можно съедать не более [latex]m[/latex]-й части оставшихся зёрен. Составьте программу, которая определяет величину первого выигрышного хода по заданным числам n и m. Если выигрышного хода нет, то нужно вывести [latex]-1[/latex].»

Анализ задачи:

  1. Первыми в голову приходят методы решения, основанные на полном переборе или на поиске производящей функции (к примеру, для [latex]m = 2[/latex] все позиции [latex]n = 2^{k}-1[/latex] — проигрышные), но количество стратегий растет достаточно быстро, а выделение закономерностей в рекурсивных последовательностях — задача нетривиальная. Следовательно, имеет смысл продолжить анализ, но уже с применением теории игр.
  2. Предложенная игра представляет собой версию игры ним. Отличие в том, что множество объектов одно, а количество допустимых на данном шаге ходов зависит от ситуации на игровом поле.
  3. Эффективный поиск выигрышного хода можно провести при помощи функции Шпрага-Гранди.
  4. Выигрышные позиции отличаются только расстоянием до проигрышной для противника (в зернах), следовательно, можно воспользоваться выигрышно-проигрышным разбиением позиций и ввести соответстенные характеристики позиций: [latex]\left\{ 1, -1 \right\}[/latex].
  5. Если все позиции, в которые можно попасть из данной, являются выигрышными для противника (при условии, что он не играет в поддавки), считать её проигрышной.

Алгоритм решения:

  1. Построение базы анализа: позиция [latex]n = m[/latex] — выигрышная (единственным доступным ходом мы заканчиваем игру), следовательно, [latex]n = m + 1[/latex] — проигрышная.
  2. Если на расстоянии [latex]\left\lfloor \frac {step}{m} \right\rfloor [/latex] от текущей позиции [latex]step[/latex] все значения равны [latex]1[/latex], пометить [latex]step[/latex] как [latex]-1[/latex]. В противном случае пометить как [latex]1[/latex].
  3. Если значение для [latex]step = n-1[/latex], то вывести на экран [latex]-1[/latex]. В противном случае вывести расстояние до ближайшей проигрышной для противника позиции.

Результаты тестирования:
Для всех [latex]n[/latex] при [latex]m = 2[/latex] программа предсказуемо выдает последовательность проигрышных ходов при [latex]n = 2^{k}-1[/latex].
На малых значениях [latex]n[/latex] при [latex]m > 2[/latex] установлена корректность алгоритма.

n m Результат
7 2 -1
8 2 1
10 3 3
7 3 -1
12 4 2
10 4 -1

Код программы:

Детали реализации:
Для хранения характеристик позиций использован динамически объявляемый массив (VLA — Variable Length Array). Для упрощения анализа использована булева переменная [latex]good[/latex].При решении применялись методы динамического программирования.
Протестировать работу программы можно по ссылке: http://ideone.com/5nmDxl.
Реализация на Java: http://ideone.com/D5R49n

Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

9 thoughts on “WoW 3: Идем к ним?

  1. «Эффективный поиск выигрышного хода можно провести при помощи функции Шпрага-Гранди.» — действительно можно!
    «область значений функции можно сузить до двух элементов: { 1, -1 }.» — но тогда это уже не функция Шпрага-Гранди!
    То что Вы делаете, называется выигрышно-проигрышный анализ или же «выигрышно-проигрышное разбиение» позиций (даже специально нашел этот термин, например, здесь ).
    А функция Шпрага-Гранди — это более тонкий механизм, который понадобится Вам для задачи «Ним, нимберы и функция Шпрага-Гранди» — которую я наконец-то доделал.

    По решению есть одно существенное замечание: для того чтобы определить, является ли позиция step выигрышной, в строке 14 Вы пишете for(int i = step; ... ; el--) и затем проверяете значение sprague[i] — т.е. изначально sprague[step], которая еще не заполнена (в ней хранится мусор) — ее не надо проверять, минимальный ход — взять 1 зерно, пропускать ход нельзя. Ну и el— явная опечатка, наверное имелось в виду i— (el в программе больше не участвует). Последний вариант программы обязательно проверяйте на тестах, если все работало раньше, то не факт, что будет работать после изменений.
    Еще в пункте «3. Если значение функции Шпрага-Гранди …» небольшая опечатка в формуле (формула расщепилась на две почему-то).

    В остальном претензий нет, все четко описано и реализовано. Вы используете метод динамического программирования для анализа позиций игры (последовательное вычисление элементов массива, используя предыдущие значения).

    • Доработал отчет и подкорректировал код программы.
      Регрессионное тестирование выполнил, результаты остались прежними.
      Спасибо за замечания и уточнения, особенно за статью.

      • Еще раз обращу внимание: for(int i = step; i >= step - step / m && !good; i--) Вы начинаете перебор возможных ходов с хода «взять ноль зерен» — который однако невозможен. Программа работает только потому, что в том мусоре, который хранится изначально в массиве int result[n + 1]; отсутствуют значения -1.

        • Добавил очистку массива от мусора.
          Проблему понял. Теперь анализ начинается с позиции n = m, из которой возможно сделать ход в одно зернышко.

  2. Ну Вы даете! Я всего-то имел в виду, что нужно исправить строчку for(int i = step; i >= step - step / m && !good; i--) на for(int i = step-1; i >= step - step / m && !good; i--), так как из позиции step можно перейти в позиции step-1 (взять 1 зерно), step-2 (взять 2 зерна), …, step — step / m (взять число зерен step/m, т.е. одну m-тую от количества зерен округленное вниз). Вы же переделали всю программу кардинально.

    Теперь по пунктам:
    1. очистка массива от мусора — необязательна, если правильно реализовать программу, то мусор не используется; но эта очистка и не мешает — будем считать что сделано на всякий случай.
    2. Вы решили экономить память — на m ячеек меньше. Ладно. Но
    2а) страдает наглядность. Вам нужно вычитать m из индекса. Но это еще полбеды, хуже что Вы вычитаете индексы по разному: result[step - m] — логично, i = step - m, … result[i] — другой способ, а ведь суть i та же самая, что и step — номер позиции, оно же число зерен.
    2б) i >= ((step - step / m) - m) && !good — а тут вообще скрытый подводный камень, так как ((step — step / m) — m) вполне себе оказывается меньше нуля. А нет, я неправ, ((step — step / m) — m) вроде как всегда больше либо равно нуля, но мне пришлось крепко задуматься, чтобы догадаться до этого.
    2в) теперь у Вас не учтен случай n

    • Привел к исходному и виду и изменил строку 17. Надеюсь, теперь я вас понял правильно. Спасибо за подробный анализ.

  3. В прошлом комментарии 2в) должен быть: теперь у Вас не учтен случай n меньше m, кстати такой тест желательно добавить. Нужно тестировать крайние случаи, а не только «нормальные».

    Но из-за того что меньше было значком, конец предложения пропал, а я и не заметил.

    Так что лучше добавить тест, где n меньше m. Он у Вас должен пройти в таком варианте … почти … в строчке 10 переменная i изменяется от 0 до m, включительно (кстати, почему до m? ведь m — уже выигрышная — это я тоже не доглядел в первый раз). А если n меньше m, то заполняется больше элементов массива, чем выделено памяти под массив.

  4. Очень здорово, что на первом курсе уже разбираются такие задачи.
    Можно данную задачу решить не за O(n^2 / m), а за O(n). Если Вас заинтересует, предлагаю подумать, как это можно сделать.
    Следующий этап — за O(log n).

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