algorithm - 二进制数字游戏之美

Question

这是一个众所周知的问题(类似问题:number of setbits in a number and a game based on setbits但答案不清楚):

The beauty of a number X is the number of 1s in the binary representation of X. Two players are plaing a game. There is a number n written on a blackboard. The game is played as following:

Each time a player chooses an integer number (0 <= k) so that 2^k is less than n and (n-2^k) is equally as beautiful as n. Then n is removed from blackboard and replaced with n-2^k instead. The player that cannot continue the game (there is no such k that satisfies the constrains) loses the game.

The First player starts the game and they alternate turns. Knowing that both players play optimally must specify the winner.

现在我想出的解决方案是这样的:

向右移动 1 位，就是将该数字减去 2^p，其中(p = 位移动到的位置 - 1)。示例:11001 --> 25 现在如果我将其更改为 10101 ---> 21 ( 25-(2^2))

玩家不能在 1 轮中进行 2 个或更多这样的右移(不是程序性右移)，因为它们的总和不能达到 2 的幂。因此，玩家只能将设置的位移动到某个位置每轮向右移动一次。这意味着只能有 R 轮，其中 R 是设置位可以移动到更正确位置的次数。因此，如果 R 为奇数，则获胜者将始终是第 1 名玩家；如果 R 为偶数，则获胜者将始终是第 2 名玩家。

Original#: 101001 41
after 1st: 11001 25 (41-16)
after 2nd: 10101 21 (25-4)
after 1st:  1101 13 (21-8)
after 2nd:  1011 11 (13-2)
after 1st:   111  7 (11-4) --> the game will end at this point

我不确定该方法的正确性，这是正确的吗？还是我错过了一些大事？

Answer 1

您的方法是正确的。这里要进行的观察是，也如您给出的示例所示，当所有的都位于最低有效位时，游戏结束。所以我们基本上需要计算需要多少次交换才能使零到达最高有效位。

举个例子，假设游戏开始的初始数字是12，则游戏状态如下:

Initial state 1100 (12) -> 
A makes move 1010 (10) -> 
B makes move 1001 (9) -> 
A makes move 0101 (5) -> 
B makes 0011 (3)
A cannot move further and B wins

这可以通过编程方式(java程序v7)实现

public int identifyWinner (int n) {

    int total = 0, numZeros = 0;

    while (n != 0) {
        if ((n & 0x01) == 1) {
            total += numZeros;
        } else {
            numZeros++;
        }
        n >>= 1;
    }

    return (total & 0b1) == 1 ? 1 : 2;
}

还要注意，即使玩家有多种选择可以采取下一步行动，如下所示，结果也不会改变，尽管导致结果的中间变化可能会改变。

再次让我们以初始数字 12 为例来看看状态流程

Initial state 1100 (12) -> 
A makes move 1010 (10) -> 
(B here has multiple choices) B makes move 0110 (6)
A makes move 0101 (5) -> 
B makes 0011 (3) 
A cannot move further and B wins

A 无法进一步移动，因为没有 k(k >=0 且 n < 2**k 因此 k =0, 1 是这里唯一合理的选择)n-2^k 是否与 n 具有相同的美感，因此 B 获胜。

也可以以 41 为起点进行多种选择，但 A 总是获胜 (41(S) -> 37(A) -> 35(B) -> 19(A) -> 11(B) -> 7(A))。

希望对你有帮助!