4

这是硬件：

Wythoff 的游戏中有两个玩家，在这种情况下有 3 堆石头。每个玩家轮流从堆中取出石头，如果他们拿起最后一块石头，则玩家获胜。每回合玩家可以从一堆中取出 N 块石头，从两堆中取出 N 块，或者从所有三堆中取出 N 块。

获胜配置是第一个玩家可以强制获胜的配置。例如，(0,0,13)、(0,11,11) 和 (5,5,5) 是获胜配置，因为第一个玩家可以立即移除所有棋子。

失败的配置是第二个玩家可以强制获胜，无论第一个玩家做什么。例如，(0,1,2) 和 (1,3,3) 正在输掉配置：任何合法的移动都会为第二个玩家留下获胜配置。

考虑所有丢失的配置 (xi,yi,zi)，其中 xi <= yi <= zi <= 100。我们可以验证 Σ(xi+yi+zi) = 173895。

我已经搜索和搜索，但无法弄清楚如何找到所有丢失（冷）的位置。通过对坐标的二进制值求和得到 nimnumber，如果 nimnumber > 0 则它是冷位置。但我最终得到 Σ(xi+yi+zi) > 1mil。谁能帮我指出正确的方向？

4

1 回答 1

1

由于是作业，我不会发布完整的解决方案，但这里有一个提示：

你已经知道 xi <= yi <= zi <= 100，所以配置的数量永远不会超过 2*101^3（轮到谁的 x2），不会超过 200 万。尝试制作一个查找表（例如，isWinningPosition[][][][]其中isWinningPosition[a][b][c][d]对应于大小为 a、b、c 的堆，轮到 d）并递归。（警告：查找表中的每个条目都需要将 、 和 作为三个独立的东西来true处理false。not computed）

于 2012-07-20T21:17:29.790 回答