作者: physixfan
所谓拈游戏的规则是这样的:(在看了沙发的评论之后我才知道其标准名字应该是Nim游戏…)
桌面上有三行硬币,每一行中分别有a1、a2、a3个硬币,其中a1、a2、a3是可以任意指定的正整数。两个人轮流拿走硬币,每一次只能从某一行中拿走任意多个硬币,谁拿走最后一枚硬币谁就赢了。
比如说a1=1,a2=2,a3=3的情况吧,这时如果轮到我拿了,我可以从第三行拿走2枚硬币,或者可以把第三行的三枚硬币全都拿走,等等;但是我不能同时从第一行和第三行里各拿走1枚硬币。这个简单的情况,可以枚举所有可能性得出结论:先拿的必输。
当a1、a2、a3是任意给定的,在什么情况下先拿的必输呢?必胜策略是怎样的呢?这是一个相当有意思的问题,答案可绝不是显而易见一目了然的。而当我当年看到这个策略长什么模样之后,完全的叹服了。今天我就先不写必胜策略了,大家可以先自己想想,如果下周或者什么时候有时间了再来写。前一阵子我为了熟悉C++自己写了一个拈游戏的人机对弈程序,大家可以点击下面的链接下载。其中包含了必胜策略,所以只要你一步走错就一定会输。
拈游戏.rar
其实拈游戏不仅仅局限于三行硬币,其实最初的问题是N行的,而且神奇的是其必胜策略对于任何N都是一样的。其实这个拈游戏是我上小学的时候奥数老师跟我玩的游戏,最近才发现这个经典的有意思的游戏还有好多人没有玩过,故写此文…
Related
Nim取子游戏,把每个堆写成2进制。
回复的这么迅速…
原来这个东西的标准名称叫Nim游戏啊…怪不得我搜索拈游戏搜不出来什么东西呢…
组合游戏论么,是有一整套系统的理论的哦。
像这个只要全部异或起来就好了……
……刚接触这个游戏的形式就是
任意在纸上画出几行圆圈然后分别删去……
记得总是输给数学课代表
这东西跟博弈论有关吧?
看看我下一篇日志就知道了
3行的时候只有(1,2,3)才是后取者胜
原来这游戏名叫Nim
把“每一次只能从某一行中拿走任意多个硬币,”改成“每一次只能从某一行中拿走 1到n 个硬币”后会有什么策略?我只想出来了n=2的情况