资源描述：
《取石子游戏类分析的分析讨论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、“取石子游戏问题”的几种变形及其解法探讨长沙市雅礼中学朱全民BashGame问题描述：只有一堆n个石子，两个人轮流取石子，规定每次至少取1个，最多取m个。最后取光者得胜。分析1.n=m+1时，先手显然必败。2.n=(m+1)x+y时，先手先取y个，若对手取k个则先手再拿走m+1-k个。3.总能保证n能被(m+1)整除，所以最终先手必胜。当y为0时，后手必胜。实例n=7,m=3(x,y)表示当前石子数和下次拿走的石子数。(7,3)->(4,y)->(4-y,4-y):先手获胜。n=8,m=3第一步无论先手去什么，后手总可以将石子数变
2、为4，无论先手再下步取什么，后手总能将剩下的石子一次取完。问题变形(SLPC2009)只有一堆n个石子，两人轮流取石子，规定每次取1到20个。后手的策略是：如果当前石子数小于等于20个则全部拿走，否则若先手取了k个，则后手取ak个。最后取光者得胜。先手是否有必胜策略？分析n不被21整除：使用同样策略，必胜。n被21整除：n=21,必败。存在某个k，使得k+ak不被21整除：第一步拿掉k个，然后对方会拿掉ak个，剩下n-k-ak个，到达n不被21整除的状态，因此必胜。其它情况，必败。WythoffGame问题描述：有两堆各若干个石子
3、，两个人轮流从某一堆或同时从两堆中取同样多的石子，规定每次至少取一个，多者不限，最后取光者得胜。方法1动态规划：设f(a,b)表示两堆分别剩a颗和b颗石子时的胜负状态。则，f(a,b)=f(a-k,b)orf(a,b-k)orf(a-k,b-k)时间复杂度达到了o(n3)改进因为，f(a,a)，先手必胜f(a,b)=f(b,a)当f(a,b)为必败态时，对于所有c≠b,f(a,c)必胜。因此，对于n，所有状态中必败的状态是o(n)级别的，我们可以不断寻找必败态，利用这些状态更新其它状态。复杂度为o(n2)。小规模情况如果甲面对（0
4、，0），那么甲已经输了，这种局势我们称为必败态。前几个必败态是：（0,0）（1,2）（3,5）（4,7）（6,10）（8,13）（9,15）（11,18）（12,20）1=2-1,2=5–3,3=7–4,4=10–6,5=13–8,6=15-9,7=18-11,8=20-12,……,结论设第i个必败态为(xi,yi)，有，思考题有三堆石子，分别为a,b,c颗。有两个人在做如下游戏：游戏者任意拿走其中一堆石子，再在剩下的两堆里任取一堆任意分成两堆（每堆至少1颗）。两人轮流如此，谁无法这样做就算输了。输入格式：有n组数据：每一行三个数
5、a,b,c，满足1≤a,b,c≤1,000,000,000。输出格式：对应n行：“1”——先手赢；“0”——后手赢。递推设f(a,b,c)表示状态(a,b,c)的胜负：f(a,b,c)=1为胜局，表示先手胜，f(a,b,c)=0为败局。f(a,b,c)可以递推计算：若存在1≤k≤a-1使得f(k,a-k,b)=0或f(k,a-k,c)=0或存在1≤k≤b-1使得f(k,b-k,a)=0或f(k,b-k,c)=0或存在1≤k≤c-1使得f(k,c-k,a)=0或f(k,c-k,b)=0那么f(a,b,c)=1否则f(a,b,c)=0
6、。小规模情况f(a,b,c)必败点如下：f(1,1,1)，f(1,1,3)，f(1,3,1)，f(1,3,3)；f(2,2,2)；f(3,1,1)，f(3,1,3)，f(3,3,1)，f(3,3,3)；f(4,4,4)；f(5,1,1)，f(5,1,3)，f(5,3,1)，f(5,3,3)；f(6,2,2)；f(7,1,1)，f(7,1,3)，f(7,3,1)，f(7,3,3)；找出规律a=1,3,5,7，(b,c)=(1,1),(1,3),(3,1),(3,3),…,a=2,6，(b,c)=(2,2),…,a=4，(b,c)=(
7、4,4),…,分析a的特点：1）a=1,3,5,7都是奇数，b2）a=2,6是偶数，它只含1个23）a=4是偶数，但它含2个2分析b,c的特点：b,c特点直接与a的特点相关。Nimk游戏问题描述：两人轮流对N堆石子进行操作，每堆分别有Pi颗。每人每次可以从最多K堆中取走任意多颗石子，但至少要取走一颗石子。谁取到最后一颗谁胜利。什么情况下先手必胜，什么情况下后手必胜预备知识定义：如果一个局面先手必胜，就称之为N局面，反之称之为P局面。Nimk问题当K=1时就是经典的Nim问题。XOR运算为对二进制进行逐位不进位加法（对每一位结果mo
8、d2）。Nim问题的解法是：对于一个局面，令S=P1XORP2XORP3XOR…XORPn。若S=0则为P局面，否则为N局面。证明若当P1=P2=….=Pn=0时，S=0，满足终状态是P局面。若S=0，即P1XOR…XORPn=0，若取堆i中的石子
