取石子游戏类分析的分析讨论.ppt

“取石子游戏问题”的几种变形及其解法探讨,长沙市雅礼中学朱全民,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第一步无论先手去什么，后手总可以将石子数变为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,问题描述：有两堆各若干个石子，两个人轮流从某一堆或同时从两堆中取同样多的石子，规定每次至少取一个，多者不限，最后取光者得胜。,方法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)为必败态时，对于所有cb,f(a,c)必胜。因此，对于n，所有状态中必败的状态是o(n)级别的，我们可以不断寻找必败态，利用这些状态更新其它状态。复杂度为o(n2)。,小规模情况,如果甲面对（0，0），那么甲已经输了，这种局势我们称为必败态。前几个必败态是：（0,0）（1,2）（3,5）（4,7）（6,10）（8,13）（9,15）（11,18）（12,20）1=2-1,2=53,3=74,4=106,5=138,6=15-9,7=18-11,8=20-12,结论,设第i个必败态为(xi,yi)，有，,思考题,有三堆石子，分别为a,b,c颗。有两个人在做如下游戏：游戏者任意拿走其中一堆石子，再在剩下的两堆里任取一堆任意分成两堆（每堆至少1颗）。两人轮流如此，谁无法这样做就算输了。输入格式：有n组数据：每一行三个数a,b,c，满足1a,b,c1,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)可以递推计算：若存在1ka-1使得f(k,a-k,b)=0或f(k,a-k,c)=0或存在1kb-1使得f(k,b-k,a)=0或f(k,b-k,c)=0或存在1kc-1使得f(k,c-k,a)=0或f(k,c-k,b)=0那么f(a,b,c)=1否则f(a,b,c)=0。,小规模情况,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)=(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运算为对二进制进行逐位不进位加法（对每一位结果mod2）。Nim问题的解法是：对于一个局面，令S=P1XORP2XORP3XORXORPn。若S=0则为P局面，否则为N局面。,证明,若当P1=P2=.=Pn=0时，S=0，满足终状态是P局面。若S=0，即P1XORXORPn=0，若取堆i中的石子，Pi-Pi，S-S，PiPi，则PiXORPi0。所以SXORPiXORPi=S=0，即S=PiXORPi0。满足P局面的所有子局面都是N局面。若S0，设S的二进制位是A1An，考虑第一位是1的。在P中取出该位同是1的，不妨设为P1。可知P1XORS1,K=231151011010101511112200(mod3)所以这是N局面，第一步取10-615-7可以到达一个P局面3567。311510160110701110000(mod3),MisreNim,基本规则同NimGame问题，胜负判定是谁不能继续取石子，谁就赢了。,分析,1）所有石子堆的数目都为1：显然，若有偶数堆石子堆，则必胜，否则必败。2）如果恰好只有一堆石子数目大于1。我们可以把这堆石子取完或者取得只剩下1，使得只剩下奇数堆数目为1的石子留给对方，由1)，必胜。3）如果有至少2堆石子的数目大于1。考虑值：若值不为0，则按照NimGame走法取石。这样，当对手某次取完石子后，肯定会出现2）的情况，则必胜。,证明,按照NimGame法则取完石子后，必定会给对手留下值为0的局面。因此不可能给对手留下2）的局面（容易证明，2）局面的值肯定不为0），而对手一次最多将一堆石子数大于1的石子堆处理掉。因此2）的情况肯定会出现。相反，若值为0，则无论如何走都会给对方留下2）或3）的情况，必败。,实例,n=4,1,1,2,2第一步若拿掉一堆为2的石堆，则只剩一堆1的石堆。必败。若拿掉一堆为1的石堆，对方也拿掉一堆为1的石堆，无论我们接下来怎么取，都只剩一堆1的石堆。必败。在一堆为2的石堆中拿掉一颗石子，只剩一堆1的石堆。必败。n=4,1,1,2,3我们可以在3的石堆中拿掉一颗石子，变为一个xor值为0的必败状态，所以必胜。,Astonegame,一堆石子有n颗，两个人轮流从中取石子，第一个人第一步最多取n-1颗，接下来每一步，假设上一步取了x颗，当前取石子的人最多可以取k*x颗，当然一个人不能一颗石子也不取。取走最后一颗石子的人获胜。假设两个人都使用最优策略，请问对于给定的n,k先手能否获胜？,分析,定义x为绝对必败态，当且仅当无论何种情况下只要走到了这个状态，那么先手必然失败的状态。假设前1.i-1个绝对必败态p1.pi-1(p1=1)。pi-1+1,pi-1+2,pi-1+m都是必胜态的充分条件是：k*mpi-1。（先手可以走到pi-1的状态同时第二个人不能一次把所有石子拿走）,分析,那么是不是m+1就是必败的呢，事实上我们也可以选择不直接跳到pi-1去，这时问题转化成了一个(x-pi-1)的子问题，即看谁会被迫先走到pi-1的绝对必败态去。接下来的第一个必败态是pi-1+pj，其中pi-1+pj=m。,实例,当k=10时，假设当前已经求出的必败态集合是23456789101113151719212427303337414651576370778594104115。我们要求后一个必败态，m=(115/10)=11,pj=13,pj-1=11;显然从116-126都是必胜的，他们可以转化到115这个必败态，那127呢？我们可以取1个石子，转移到126，显然这时126无法取到足够多的石子转移到115，它成为必败态，于是127也是必胜态。而128=115+13则成为了必败态，因为无论是转移到127还是126它都使下一个状态必胜，这里的pj=13,pi-1=115,所以pi=128。,SGU429,有n堆石子，将这n堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。问：对于任意给出一个初始一个局面，是否存在先手必胜策略。,分析,设fleftlr表示对于Al,Ar当Al取多少时（其余的A值不变），这个状态是必败的。同理可设frightlr。只考虑(Al,Ar)的组合，我们说(X,Y)是个必败态当且仅当X,Al+1,.,Ar-1,Y是一个先手必败的状态。,分析,首先得到2个初始的必败态，即(0,frightl+1r)和(fleftlr-1,0),同时必败态应满足以下条件：每行有且仅有一个必败态。每列有且仅有一个必败态。这是因为如果（p,x）,(p,y)都是必败态，不妨设x=gn-1时，双方都希望投反面（都希望下步自己先手），fn=PR6*fn-1+PR5*gn-1gn=PR8*fn-1+PR7*gn-1fn-1gn-1时，fn=PR2*fn-1+PR1*gn-1gn=PR4*fn-1+PR3*gn-1。,StaircaseNim,问题描述：游戏开始时有N堆石子排成一排，从左至右编号为1到n。游戏者在每次操作时可以将编号为j(1q0我们可以递推求得子游戏任意状态的SG函数值。用SG定理可以求得和游戏的任意状态的SG函数值。,思考题,如果多堆的nimk游戏，第2k次操作只能拿走偶数标号堆的石子，第2k+1次操作只能拿奇数标号堆的石子。问题要如何解决？如果例题1中的堆数扩展到m堆，问题要如何解决。想出几个关于take&break模型的转化问题。（ACMICPC2006beijingafunnystonegame是个经典的此问题的转化）想出几个关于staircasenim模型的转化问题。（如POI2006Stage）,AFunnyStoneGame,David玩一个石子游戏。游戏中，有n堆石子,被编号为0.n-1。两名玩家轮流取石子。每一轮游戏，每名玩家选取3堆石子i,j,k(ij,j=k,且至少有一枚石子在第i堆石子中)，从i中取出一枚石子，并向j，k中各放