我们遇到了一个问题,我将其简化为以下内容:给您一个全为二进制数(例如 11111)和一组相同长度的二进制数(00101、10000、01100、00100、11100)。有两个玩家 A 和 B。在每一轮,玩家可以从主二进制数 (11111) 中减去任何一个较小的数字,这样 2 的二进制与就是较小的数字。然后下一个玩家可以从结果中减去,依此类推。不能再减去的玩家就输了。例如。
A B
11111 11010 // Now A cannot subtract
-00101 -10000 // anymore in the next turn.
------- ------ // So B wins the game.
11010 01010
------- ------
如果两个玩家都发挥最佳(为他们的胜利做出最佳选择),我必须找出给定二进制数字组合的哪个玩家获胜。
我尝试过 O(n^2) 方法,但有更快的方法吗?
编辑: O(n^2) :其中 n 是状态数。对于长度为 6 (111111) 的二进制数,可能有 2^6 种状态。所以我的复杂度是 O((2^6)^2)。
编辑:生成所有可能状态的我的代码:
void makeAllStates() /* Bottom Up Approach. Starting from 00000 and going to 11111 */
{
// bool states[i] : True if state[i] is a winning position.
// bool isWord[i] : True if the given state matches a smaller number. (eg. If the main number has been reduced to 10110 and there is a smaller number 10110, then isWord[i] is true.
// bool visited[i] : True If the given state has been visited
// int statecount : Total number of states
int temp;
for(int xx=1;xx<stateCount;xx++)
{
for(int yy=1;yy<stateCount;yy++)
{
if(xx&yy)
continue;
if(!(isWord[xx] || isWord[yy]))
continue;
if(!visited[yy])
continue;
temp = xx^yy;
if(isWord[temp])
continue;
if(states[temp])
continue;
if(isWord[xx] && isWord[yy])
states[temp] = false;
else
{
if(isWord[xx])
states[temp] = !states[yy];
else
states[temp] = !states[xx];
}
visited[temp] = true;
if(temp == stateCount-1 && states[temp])
{
return;
}
}
}
}