可以证明:任何一个偶状态在其中一个数变小后一定成为奇状态,而一个奇状态一定可以通过改变一个数变成偶状态.
...对于后一点,对于一个从高位到低位某一位和为奇的奇状态,必定有一个数的二进制表示在此位为1,对于后面的较低位和为奇的情况,只要把这个数对应位取反即可得到一个偶状态.
...XOR 和判断:
如果有奇数个二进制数在第K位为1 那么在这一位上的和为奇,同样的,偶数个1和为偶.
...很明显位运算xor满足我们的要求,偶数个1异或和为0,奇数个为1;
由此,终于可以给出算法
1 int Nimm_Game(int n)//假设n个数存在数组f[]中,有必胜策略返回1
2...由于n是偶数 所以(n & 3)只可能得到 1 或 3;
1对应 二进制数 (01)所以是奇数个1 此时f [0,n]=1;
3对应 二进制数 (11) 此时f[0,n]=0;
当n为偶数时,m