6
  • 2 个玩家 A 和 B 正在玩一个涉及数字n的游戏
  • 玩家 A 迈出第一步，两名玩家交替下棋。
  • 在每一步中，玩家选择数字 n，选择一个数字i，使得2^i < n并将n替换为k = n - 2^i如果k的二进制表示中 1 的数量大于或等于n的二进制表示中 1 的数量
  • 当没有玩家可以移动时，游戏结束，即不存在这样的i

例如：

n = 13 = b1101

只可能 i=1

k = n - 2^i = 11 = b1011

同样，只有可能 i = 2

k = n - 2^i = 7 = b111

由于玩家 A 不能再移动，玩家 B 获胜

我已经推断出，在任何一步，我们只能选择一个i，使得在n的二进制表示中对应的位置有一个0。

例如：如果 n=1010010，那么 i 只能是 {0,2,3,5}。

但我不能再进一步了。极小极大算法并没有让我感到震惊。我将不胜感激。提前致谢

4

1 回答 1

3

假设n不太大，我们可以使用动态规划来解决这个问题。定义一个数组 A[1:n]，其中 A[i] 表示玩家 i 是否会在输入 i 上获胜。让我们使用解释：

   A[i] = 1, if A wins on input i,
   A[i] = 0, if A loses on input i.

现在 A 可以自下而上计算如下：

A[1] = 0, A[2] = 1.
For j=3:n { 
      Assign A[j] = 1 if there exists a number i such that (A[j-2^i] = 0) AND 
                              (number of 1's in i >=  number of 1's in j)
      Otherwise  Assign A[j] = 0 
}
于 2012-09-25T00:07:02.910 回答