Ним и число Гранди
Решайте беспристрастные игры с помощью XOR
«Ним и число Гранди» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Знакомьтесь: игра Ним
В игре Ним есть несколько кучек камней. За ход можно убрать любое количество камней из одной кучки, а победителем становится тот, кто забирает последний камень. 🪨
Волшебная величина: XOR
Исход всей игры определяется XOR размеров всех кучек. Это единственное число показывает, кто победит.
Правило ним-суммы
Если XOR кучек, называемый ним-суммой, равен нулю, игрок, которому предстоит ходить, проигрывает. Если он ненулевой, этот игрок выигрывает.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pПочему ноль означает неприятности
Из позиции с нулевой ним-суммой любой ход нарушает равновесие и оставляет сопернику ненулевую сумму, которую тот всегда может восстановить.
Находим выигрышный ход
Если ним-сумма ненулевая, всегда существует ход, после которого она снова станет равной нулю. Так Вы оставляете соперника в проигрышной позиции.
За пределами Нима: числа Гранди
Для других беспристрастных игр каждой позиции сопоставляется число Гранди. Оно обобщает идею ним-суммы почти на любую игру с изъятием объектов.
Операция mex
Значение Гранди состояния — это mex: наименьшее неотрицательное целое число, отсутствующее среди значений Гранди его ходов.
def mex(s):
i = 0
while i in s:
i += 1
return iВычисляем числа Гранди рекурсивно
Рекурсивно обработайте все достижимые состояния, соберите их значения Гранди, а затем найдите mex этого множества.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Нулевое число Гранди означает проигрыш
Игровое состояние со значением Гранди 0 является проигрышным — точно так же, как позиция с нулевой ним-суммой. Ненулевое значение означает выигрыш.
Теорема Шпрага — Гранди
Для независимых игр, идущих одновременно, выполните XOR их чисел Гранди. Этот результат Шпрага — Гранди превращает любую сумму игр в Ним. ✨
Когда это применимо
Теория Гранди требует беспристрастной игры: у обоих игроков одинаковые ходы, а побеждает тот, кто ходит последним. Проверьте это перед применением теории.
Быстрая проверка
Вы начинаете игру Ним с кучками размера 1, 2 и 3. Вы выигрываете?
Итоги
В Ниме всё определяется XOR кучек: ноль означает проигрыш, ненулевое значение — выигрыш. Числа Гранди и mex расширяют эту идею на множество беспристрастных игр. 🏆
Часто задаваемые вопросы
Урок «Ним и число Гранди» бесплатный?
Да — полный текст урока «Ним и число Гранди» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Ним и число Гранди»?
Решайте беспристрастные игры с помощью XOR Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Ним и число Гранди»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Выигрышные и проигрышные состояния в играх
- Ним и число Гранди
- Встреча посередине
- Быстрая отладка: стресс-тесты и сортировка ошибок