2

我想知道是否有一种简单的方法可以在这里看到这种模式。我已经考虑了好几个小时，但无法完全制定它。

游戏的运作方式是有 2 个玩家，N石头塔，当轮到玩家时，他必须从塔中移除至少 1 块石头，移除最后一块石头的玩家获胜。

这是我到目前为止绘制的内容，作为获胜者的塔高度地图：

// {1} ---> "First" (remove the single stone)
// {2} ---> "First" (remove both stones)
// {n}, n > 2 ---> "First" (remove all the stones)
// {1, 1} ---> "Second" (because your only option is to remove 1 stone and then your opponent only has to remove 1 stone to win)
// {1, 2} ---> "First" (because you can remove 1 stone from the 2nd tower and then your opponent is left with {1, 1} which makes him lose as I explained in the last one)
// {1, 3} ---> "First"
// {1, n}, n > 1 ---> "First"
// {2, 2} ---> "Second"
// {2, 3} ---> "First"
// {2, 4} ---> "First"
// {2, n}, n > 2 ---> "First"
// {m, n} ---> m < n ---> "First"
// {1, 1, 1} ---> "First"
// {1, 1, 2} ---> "First"
// {1, 1, 3} ---> "First"
// {1, 1, n} ---> "First"
// {1, 2, 2} ---> "First"
// {1, 2, 3} ---> "Second"
// {1, 2, 4} ---> "First"
// {1, 2, 5} ---> "First"
// {1, 2, n}, n > 3 ---> "First"
// {2, 2, 2} ---> "First"
// {2, 2, 3} ---> "First"
// {2, 2, n}, n > 1 ---> "First"

我得出的事实：

  • 如果每座塔有1个石头，如果塔数为奇数，则轮到的玩家获胜，否则输
  • 如果塔的数量是N并且任何塔的高度大于N+1，则结果与该塔的高度相同N+1

除此之外，我想不出足够的模式来编写线性解决方案。

有什么帮助吗？

4

1 回答 1

3

这个游戏被称为 NIM。获胜的策略是在每座塔中棋子数量的 XOR 为 0 的位置上留下一个位置。这迫使对手进入具有非零 XOR 值的配置。然后，第一个玩家又可以再次到达 XOR 值为 0 的位置。

例如，从 {1,2,4} 开始，获胜的一步是走 {1,2,3}。请注意，1 XOR 2 XOR 3 = 0。假设对手从最后一堆 {1,2,1} 中拿走 2 块石头，下一个获胜的举动将完全移除第二堆：{1, 0, 1} 再次进行 XOR值 0；等等。

于 2016-10-18T04:28:27.153 回答