总而言之,游戏中有n个塔高m,每转一圈,玩家可以将一个塔减少到一个除以其高度但不等于其高度的数字,目标是让对手在轮到他时没有可能的移动。
例如,如果N=2,M=2那么第一个玩家输了,因为他唯一能做的动作是将一个塔降低到1号高度,之后另一个玩家唯一能做的动作是将另一个塔降低到1号高度,而现在第一个玩家没有动作要做。
我开始写这篇文章,但它变得太复杂了,我无法真正看到非素数上的“模式”,比如M。有没有更好的方法让我思考这个问题?

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

我计算一号或二号选手获胜的方法是
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;
}

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

最佳答案

我们可以排除从高度1开始的塔我们也可以排除从素数开始的高度如果它们都是质数,那么每个玩家只有一个可能的移动。一次一个塔降到1高,直到都是1,所以谁赢取决于n是否奇怪。
因此以m不是1且不是素数的情况为例。
最快的游戏是将所有高度降低到1,这将采取n移动如果移动结束时剩余的移动次数是偶数,则移动的玩家获胜如果n是奇数,则第一个玩家获胜。
所以球员们都想在轮到他们的时候再做剩下的动作。玩家可以通过将塔降低到一个基本高度来增加1点剩余的移动。另一个玩家不能在同一个塔上重复这个动作,因为那个塔上只剩下一次移动。这样做的次数是n所以玩家是否能够在回合中向左移动的次数是偶数取决于n是否是奇数。

07-24 09:44
查看更多