Nim游戏(博弈论中的组合数学问题)
显示屏黑屏-证婚人致辞
Nim游戏——博弈论中的经典问题（组合数学里的知识）
Nim取子游戏
Nim取子游戏的解依赖于奇偶性，是组合数学里的一个重要问题
Nim取子游戏就是两个人面对若干堆硬币（石子、豆粒„„）进行的游戏。设有k>=1堆
硬
币，各堆分别含有n1，n2„„nk枚硬币，按下列规则取，直到最后没硬币可取，那个人
就判输！！
规则：
1、 有两名选手，分别为I 和II
2、
两名选手交替进行取硬币活动，至少在一堆中取一枚硬币
3、
对于任何一种局面，和局面的过去与未来无关
4、 最后无硬币可取的人判输！！
推理证明：
假设两个游戏人I 、II。假设有两堆硬币n1、n2。游戏人I先
去，游戏人I能否获胜与
n1、n2的值的大小无关，而取决于n1是否等于n2.
假设n1
不等于 n2，先游戏人I取较大的堆中使其与较小的堆中硬币数目相等。然后
游戏人II取任意一堆中
的任意枚硬币，然后游戏人I取另外一堆中与游戏人II相同的数目，
直到最后，可以看出最后游戏人
I 获胜。
若n1 ==
n2，则游戏人I先取，游戏人II按上面的游戏人I的取法去取，最终可以看出
游戏人II 获胜。
举个例子：
(8 , 5) ---- 游戏人I --- (5
, 5) ----游戏人II --- (5 , 2) ---- I - (2 , 2) ---
II —>(0,2) ---- I -- (0,0)
从两堆石子的取法可以推广到
k堆石子的取法，先来看一下，两堆石子的具体取法是怎样进
行的？
先将n1和n2表示成二进制的数的形式!!!
例如 57 = 2^5 + 2^4
+ 2^3 + 2^0 = 111001
这样我们就可以将一堆硬币看成有2的幂数的子堆组成，于是57就可以看成有2^5 ， 2^4
，
2^3 ， 2^0的各子堆组成。在两堆Nim取石子游戏中，各种大小的子堆的总数只能是0,1
,2。
各种子堆的总堆数是偶数当且仅当游戏中的2堆具有相同的大小，也就是说，游戏人II获
胜。反之，游戏人I获胜。
现在考虑各堆大小分别为n1，n2，„„nk的一般的Nim取子游戏。将数ni表示成二进制数：
N1 = as„„a1 a0
N2 = bs„„b1 b0
„„„„
Nk = es„„e1 e0
当且仅当
as + bs +
….+es = 偶数
ai + bi + …. + ei = 偶数
a0 + b0 + ….＋e0 = 偶数
Nim
取子游戏才是平衡的，否则，就是不平衡的
于是我们有：
游戏人I能够在非平衡的Nim取子游戏中获胜，而游戏人II能够
在平衡Nim取子游戏中获胜。
{为了判断是否是平衡的，可以运用位运算中的异或操作来实现}
Input(n);
sum = 0;
For(I = 1;I <= n;I ++)
Do:
Input(num);
Sum ^= num;
If(sum > 0)
非平衡状态
Printf(“游戏人I获胜”);
Else
Printf（“游戏人II获胜”）； <参考poj2234
hdu 1730>
举个例子：
7、9、12、15
2^3=8 2^2=4 2^1=2 2^0=1
_________
__________________________________________________
____________________
大小为7的堆 0
1 1 1
大小为9的堆 1
0 0 1
大小为12的堆 1
1 0 0
大小为15的堆 1
1 1 1
由此可以看到这局游戏是非平衡的，其中3
号位、2号位、0号位都是非平衡的。游戏人I
可以选择大小为12的堆并取走11枚硬币，只剩下1枚
硬币，1 = 0001，使其变成平衡的。
同理，也可以选择大小为9的堆取走5枚硬币剩下4枚
，或者，选择大小为15的堆取走
13枚，剩下2枚硬币。
http:~limchuwecgt