use*_*670 4 algorithm optimization game-theory time-complexity
总结一下游戏，有 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;
}
并且它通过了挑战问题的所有测试用例。所以我在不明白为什么的情况下“解决”了它。
首先要考虑的是，当你缩小一座塔时，将其高度除以它的一个除数（除了 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 是每个堆中对象数量的异或。阅读维基百科页面以获取更多信息和示例。当游戏的 nim-sum 不为 0 时，总是有可能采取行动使其为 0。否则不可能。因此，以 0 nim-sum 开始游戏意味着第一个玩家获胜，否则第二个玩家获胜。
在你的例子中，如果游戏开始时塔的数量是偶数，那么 nim-sum 是 0，因为塔都具有相同的高度，并且第一个玩家获胜。否则，如果塔的数量是奇数，则第二个玩家获胜。唯一的例外是高度为 1（这将是一个空的 Nim 游戏），这使得第二个玩家默认获胜。
这就是为什么你的“疯狂猜测”起作用了。