3

总结一下这个游戏，有 N 个高度为 M 的塔，每回合玩家可以将塔减少到除以它的高度但不等于它的高度的数字，目标是让你的对手在轮到他了。

例如，如果N=2,M=2第一个玩家输了，因为他唯一能做的就是将其中一个塔降低到高度 1，之后另一个玩家可以做的唯一动作是将另一个塔降低到高度 1，现在第一个玩家有没有动作可做。

我开始写这个，但它变得太复杂了，我无法真正看到非素数M的“模式”，例如4. 有没有更好的方法我应该考虑这个？

1 --> Lose
1 1 --> Lose
1 1 1 --> Lose
etc. 

2 --> Win
2 2 --> Lose
2 2 2 --> Win
2 2 2 2 --> Lose
etc. 

3 --> Win
3 3 --> Lose
3 3 3 --> Win
3 3 3 3 --> Lose
etc.

4 --> Win
4 4 --> Lose (see tree below)

                   4,4                        1's turn
                  /   \
                 /     \
                /       \
               /         \
              /           \
            2,4           1,4                 2's turn  
           / \  \         /  \
          /   \  \       /    \
         /     \  \     /      \
        1,4   2,2 1,2  1,1     1,2            1's turn         
       /  \    \     \           \
      /    \    \     \           \
     1,1  1,2   1,2    1,1        1,1         2's turn
          /      \
         /        \
        1,1       1,1                         1's turn

我计算玩家 1 或 2 是否会赢的方法是

static int Winner(int n, int m)
{
    if(m == 1)
        return 2;
    else if(IsPrime(m))
        return n % 2 == 0 ? 2 : 1;
    else
    {
       // ... ??
    }
}

编辑：哇，我只是做了一个疯狂的猜测

static int Winner(int n, int m)
{
    if(m == 1)
        return 2;
    else
        return n % 2 == 0 ? 2 : 1;
}

它通过了挑战问题的所有测试用例。所以我在不明白为什么的情况下“解决”了它。

4

2 回答 2

4

首先要考虑的是，当你减少一座塔时，将它的高度除以它的一个除数（除了 1）就像删除它的一个或多个主要因素。如果你用它的主要因素列表来表示每个塔的高度，那么游戏就变成了Nim的一个变体。在每一轮，玩家删除这些列表之一中的一个或多个数字，当他删除最后一个时，玩家获胜。

具有 2 个高度为 6 的塔的示例游戏：

Tower 1 (height 6) : 2 3  <- First player removes one
Tower 2 (height 6) : 2 3

Tower 1 (height 2) : 2
Tower 2 (height 6) : 2 3  <- Second player removes one

Tower 1 (height 2) : 2    <- First player removes one
Tower 2 (height 2) : 2

Tower 1 (height 1) : 
Tower 2 (height 2) : 2    <- Second player removes one and wins

一旦你理解了这一点，你只需要知道如何用 N 堆 M 对象赢得 Nim 游戏。Nim 已经在数学上解决了任意数量的初始堆和对象。

因为在你的游戏中，玩家通过移除最后一个主要因素来获胜，所以它类似于 Nim 的“正常游戏”，玩家选择最后一个对象获胜。在这种情况下，获胜策略是以 nim-sum 为 0 完成每一步，nim-sum 是每个堆中对象数量的异或。阅读 Wikipedia 页面以获取更多信息和示例。当游戏的 nim-sum 不为 0 时，总是有可能做出使之为 0 的动作。否则是不可能的。因此，以 0 nim-sum 开始游戏意味着第一个玩家获胜，否则第二个玩家获胜。

在您的情况下，如果游戏开始时塔的数量是偶数，则 nim-sum 为 0，因为塔的高度相同，第一个玩家获胜。否则，如果塔的数量是奇数，则第二个玩家获胜。唯一的例外是高度为 1（这将是一个空的 Nim 游戏），这使得第二个玩家默认获胜。

这就是为什么您的“疯狂猜测”起作用的原因。

于 2016-08-14T21:52:17.837 回答
0

我们可以排除以高度 1 开头的塔。我们也可以排除以素数开头的高度。如果它们都是素数，那么每个玩家只有一个可能的移动。一个塔一次减少到高度 1，直到它们都为 1，所以谁赢取决于是否n是奇数。

因此，以m不是 1 且不是素数的情况为例。最快的游戏是将所有高度降低到 1，这将采取n行动。如果移动结束时剩余的移动数是偶数，则移动的玩家获胜。n如果是奇数，则第一个玩家获胜。

因此，玩家在轮到他们之后试图进行剩余的移动。玩家可以通过将塔降低到主要高度来将剩余移动增加 1。另一个玩家不能在同一塔上重复此操作，因为该塔上只剩下一个动作。这样做的次数是，n玩家是否能够使轮到他们剩下的移动次数偶数取决于是否n是奇数。

于 2016-08-14T22:28:21.257 回答