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枚硬币。