c++ - 数字中的设置位数和基于设置位的游戏

Question

我正在尝试这个关于位操作的问题:

数字的美妙之处在于该数字中设置的位数。 A 和 B 开始玩一个游戏，棋盘上写着数字 N，轮到该走的玩家走到棋盘上，写下一个新数字 N-K，其中 k<=N，K 的美度为 1。这也很重要N-K 的美必须等于 N 的美。最后一个成功完成他的移动的玩家赢得了游戏。

他们都以最佳方式玩游戏。

附言我不是在这里寻找代码。我想知道如何处理这个问题？

Answer 1

这是一个典型的博弈论问题。玩家最佳发挥意味着任何玩家都会做出最大化获胜机会的举动(考虑到当玩家 2 有机会时他也愿意这样做)。

现在在这种情况下让我们看看允许的移动是什么:

根据要求，数字的美应保持不变，k 应具有美1 即 仅设置 1 位(例如。 00000100)

为了进一步说明，让我们假设我们只有 8 位数。

如果你仔细观察，为了保持 N 的美丽，k 中设置的位位于 N 的(其中一个)索引处 有一个 0 和 1 在它的左边相邻。我举个例子:

假设 N 是 01010001。现在 k 可以是 00100000, 00001000。如果您看到 N-k，美丽依然存在。操作后，您会注意到 1 向右移动，因此 0 向左移动。例如，当 N=01010001 和 k=00100000 (N-k) = 00110001 时。

此外，游戏的结束位置将是所有 0 都在左边，所有 1 都在右边(00000111).给定一个数字 N，您可以计算可能的移动次数。如果是奇数，则开始的玩家获胜，否则他输了。

现在计算这样的移动次数是简单的枚举问题。