首页 > 技术文章 > 编程之美 1.11 1.12 1.13 NIM游戏及其变种

Linkabox 2013-10-11 17:59 原文

NIM(1)

游戏规则:N块石头排成一行,位置固定,两个玩家依次取石头,每个玩家可任取其一或相邻的两块,取光者胜

解题思路:讨论N=1、2、3、4、>4的情况

取胜法则:先取者从中间取保持两边数目对称,依据别人所取位的对称位取。

 

NIM(2)

游戏规则:有N块石头,A先将其分成M堆,取石顺序为先B后A,可选任一堆取任意个(大于1)的石头

解题思路:分析N为偶数与奇数时的区别

偶数:平均分两份,XOR(M1,M2)=0,无论B如何取都会是XOR(M1,M2)!=0,A总能修正这种状态。

奇数:A无论如何分堆,XOR(M1,M2,M3….)!=0,所以总是先取者胜。

 

NIM(3)

游戏规则:有两堆石头,每人每次从两堆取相同数目的石头或仅从一堆中取任意数量,取光者胜。

解题思路:参考质数筛子法,先列举(10,10)所可能的情况,筛选掉所有安全局面。

先取者必胜称为“安全局面”,反之为“不安全局面”

image

得出如下递推式:

1.a1=1 , b1= 2

2.an为未出现在2n-2内的最小整数

3.bn=an+n

通项公式为:an=[a * n]  bn=[b * n]    a= (1 + sqrt(5)) /2   b=(3 + sqrt(5)) / 2

数学不太好这个不知道如何推导出来的,证明也看不大懂。

推荐阅读