← 完整题目索引

PROJECT EULER · #0301

尼姆游戏

Nim

仅题目 · 已解决原题 ↗

Nim 是一种用石子堆玩的游戏,两个玩家轮流从任意堆中移走任意数量的石子,直到没有石子剩下为止。

我们将考虑 Nim 的三堆正常播放版本,其工作原理如下:

  • 游戏开始时有三堆石子。
  • 在每个玩家的回合中,玩家可以从任何单个堆中移除任意正数的石子。
  • 第一个无法移动的玩家(因为没有剩余棋子)失败。

如果 (n1,n2,n3) 指示由大小为 n1n2n3 的堆组成的 Nim 位置,则有一个简单的函数,您可以查找或尝试自己推导,X(n1,n2,n3) 返回:

  • 如果采用完美的策略,即将移动的玩家最终会失败,则为零;或
  • 如果采用完美的策略,即将移动的玩家最终会获胜,则该值为非零。

例如X(1,2,3)=0,因为无论当前玩家做什么,对手都可以做出反应,留下两堆大小相等的棋子,此时当前玩家的每一步棋都可以被对手镜像,直到没有棋子剩下;所以当前玩家输了。举例说明:

  • 当前玩家移动到(1,2,1)
  • 对手移动到 (1,0,1)
  • 当前玩家移动到(0,0,1)
  • 对手移动到 (0,0,0),因此获胜。

对于多少个正整数 n230X(n,2n,3n)=0

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。