Nim 与 Grundy 数
使用 XOR 解决公平组合博弈
Nim 与 Grundy 数 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 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为什么零意味着不利
从零尼姆和出发时，每一步操作都会打破平衡，把一个非零的和交给对手，而对手总能将其恢复为零。
寻找获胜操作
当尼姆和不为零时，总能找到一种操作将其变回零。这样就能把对手置于必败局面。
超越尼姆：Grundy 数
对于其他无偏博弈，我们为每个状态使用一个Grundy 数。它将尼姆和的思想推广到了几乎所有取子游戏。
mex 操作
一个状态的 Grundy 值就是mex：在该状态所有操作所到达状态的 Grundy 值中，缺失的最小非负整数。
def mex(s):
i = 0
while i in s:
i += 1
return i通过递归计算 Grundy
递归处理所有可到达的状态，收集它们的 Grundy 值，然后对这个集合取mex。
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy 为零就是败局
单个游戏状态的Grundy 0表示必败局面，就像尼姆和为零一样。不为零则表示必胜。
斯普拉格—Grundy 定理
对于同时进行的独立游戏，对它们的 Grundy 数进行 XOR。这一斯普拉格—Grundy结论可以将任意游戏和转化为尼姆游戏。✨
适用条件
Grundy 理论要求游戏是无偏的：双方拥有相同的操作，并且最后行动的玩家获胜。使用它之前请先确认这一点。
快速检查
您开始进行一场石子堆大小为 1、2、3 的尼姆游戏。您能获胜吗？
回顾
尼姆游戏的关键在于石子堆的XOR：为零则输，不为零则赢。Grundy 数和 mex 将这一方法扩展到了许多无偏博弈。🏆
常见问题解答
「Nim 与 Grundy 数」课时是免费的吗？
是的 — 「Nim 与 Grundy 数」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「Nim 与 Grundy 数」这节课中我会学到什么？
使用 XOR 解决公平组合博弈 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「Nim 与 Grundy 数」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 博弈中的胜负状态
- Nim 与 Grundy 数
- 折半搜索
- 快速调试：压力测试与分流排查