algorithm - 如何找到哪个玩家将获胜

Question

两个玩家玩下面的游戏。游戏开始时他们从 n (1<=n<=100000) 堆石子开始。在游戏的每一步，玩家选择一堆并从这堆中移除至少一颗石头，然后将零个或更多石头从这堆中移到任何其他仍然有石头的堆中。如果玩家没有更多可能的 Action ，他就输了。给定初始堆，确定谁获胜:第一位玩家或第二位玩家，如果两人都玩得很好。

Answer 1

这是 Nim 的变体.理解 Nim 的解决方案应该有助于您更好地理解这个游戏。

对于 Nim，游戏从 n 堆石子开始。反过来，每个玩家选择一堆并从堆中取出至少一个，可能更多的石头。当没有更多的石头剩余时，游戏结束。

上面链接的维基百科文章对获胜策略有很好的解释，其中涉及计算堆大小的二进制数字和。仔细阅读，您应该能够解决这个变体。