Nim游戏

一，通常的定义：

通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

二，只有两堆石子时的最优策略

1.轮到你时只剩一堆石子

直接拿着所有的石子，赢。

2.轮到你时剩两堆石子（两堆石子不一样多）

从多的那堆石子中拿走一部分石子，使两堆石子剩下的一样多。
然后，不管对手拿走几个石子，你都从另一堆中拿走同样多的石子。

3.轮到你时剩两堆石子（两堆石子一样多）

必输，只要对手采用2中的策略。

三，有多堆石子的情况

结论：

设各堆石子的个数为n1,n2,n3,n4……nn;
设：K = n1 ^ n2 ^ n3 ^ n4 ……^nn
如果轮到你时K==0，那么你必输。
如果轮到你时K != 0，那么你只要拿走部分石子使剩下的石子数进行异或==0，那么你就赢了。

四，对于只有三堆石子的情况

为了使拿走后三堆石子数异或为0 = n1 ^ n2 ^ n3
那么存在一个n（假设为n1）n1 = n2 ^ n3
枚举两两的异或和，只有第三个的值大于这个异或值，就输出第三个值减去另外两个数的异或值就是答案了