Nim游戏
2018-03-28 本文已影响2人
第四单元
一，通常的定义：
通常的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
枚举两两的异或和，只有第三个的值大于这个异或值，就输出第三个值减去另外两个数的异或值就是答案了
