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

《取石子游戏类分析的分析讨论》由会员分享，可在线阅读，更多相关《取石子游戏类分析的分析讨论（45页珍藏版）》请在金锄头文库上搜索。

1、“取石子游戏问题”的几种变形 及其解法探讨长沙市雅礼中学 朱全民Bash Game问题描述： 只有一堆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，无论先手再下步取什

2、么，后手 总能将剩下的石子一次取完。问题变形(SLPC2009)只有一堆n个石子，两人轮流取石子，规定 每次取1到20个。后手的策略是：如果当前 石子数小于等于20个则全部拿走，否则若 先手取了k个，则后手取ak个。最后取光者 得胜。先手是否有必胜策略？分析n不被21整除 ：使用同样策略，必胜。n被21整除：n=21,必败。存在某个k，使得k + ak不被21整除 ：第一步拿掉k个，然后对方会拿掉ak个，剩下n-k-ak 个 ，到达n不被21整除的状态，因此必胜。其它情况，必败。Wythoff Game 问题描述： 有两堆各若干个石子，两个人轮流从某一 堆或同时从两堆中取同样多的石子，规定 每

3、次至少取一个，多者不限，最后取光者 得胜。方法1动态规划：设f(a , b)表示两堆分别剩a颗和b颗石子时 的胜负状态。则， f(a ,b) = f(a-k ,b) or f(a ,b-k) or f(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），那么甲已经输了，这 种局势我们 称为必败态。前几个必

4、败态是：（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”先手

5、赢；“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)，

6、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都是奇数，b 2）a=2,6是偶数，它只含1个2 3）a=4是偶数，但它含2个2分析b,c的特点 ： b ,c特点直接与a的特点相关。Nimk游戏 问题描述：两人轮流对N堆石子进行操

7、作，每堆分别有 Pi颗。每人每次可以从最多K堆中取走任意 多颗石子，但至少要取走一颗石子。谁取 到最后一颗谁胜利。什么情况下先手必胜 ，什么情况下后手必胜 预备知识定义：如果一个局面先手必胜，就称之为N局 面，反之称之为P局面。Nimk问题当K=1时就 是经典的Nim问题。XOR运算为对二进制进行逐位不进位加法（对 每一位结果mod 2）。Nim问题的解法是：对于一个局面，令S=P1 XOR P2 XOR P3 XOR XOR Pn。若S=0则 为P局面，否则为N局面。证明若当P1=P2=.=Pn=0时，S=0，满足终状态是P局面。若S=0，即P1 XOR XOR Pn=0，若取堆i中的石子，

8、Pi-Pi， S-S，PiPi，则Pi XOR Pi0。满足P局面的所有子局面都是N局面。若S6 15-7可以到达一个P局面3 5 6 7。 3 1 1 5 1 0 1 6 0 1 1 0 7 0 1 1 1 0 0 0 0 (mod 3)MisreNim 基本规则同Nim Game问题，胜负判定是谁 不能继续取石子，谁就赢了。分析1）所有石子堆的数目都为1： 显然，若有偶数堆石子堆，则必胜，否则必败。2）如果恰好只有一堆石子数目大于1。 我们可以把这堆石子取完或者取得只剩下1，使得只剩下奇数堆数目为1的石子留给对方，由1)，必胜。3）如果有至少2堆石子的数目大于1。 考虑值： 若值不为0，则

9、按照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的

10、石堆。必败。n = 4,1,1,2,3我们可以在3的石堆中拿掉一颗石子，变为一个xor值为0的必败状态，所以必胜。A stone game一堆石子有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都

11、是必胜态的充分 条件是：k*mL时，fleftij=x。同理可确定frightij。实例frightl+1r=8，fleftlr-1=6。失败状态为： (0,8),(6,0),(1,1),(2,2),.,(7,6),(8,7),(9,9),(10, 10)。SPOJ4060 有n个石子放成一堆。A和B轮流操作，A先 手。操作为投掷一枚硬币，如果正面朝上 、则从石子堆中取出一枚石子。A有P的概 率投出他想投的面，B有Q的概率投出他想 投的面。（P,Q0.5）问A赢的期望。分析A先手，双方都希望投正面，A，B得到石 子的概率分别是： PR1 = p/(1-(1-p)(1-q); （等比求和） PR

12、2 = (1-p)q/(1-(1-p)(1-q)B先手，双方都希望投正面，A，B得到石 子的概率分别是： PR3 =(1-q)p/ (1-(1-p)(1-q)PR4 = q/(1-(1-p)(1-q); 分析A先手，双方都希望投反面，A，B得到石 子的概率分别是：PR5 = (1-p)/(1-pq);PR6 = P(1-q)/(1-pq);B先手，双方都希望投反面，A，B得到石 子的概率分别是：PR7 = q(1-p)/(1-pq);PR8 = (1-q)/(1-pq);分析设fn表示剩n个石子，A先手，A获得胜利 的概率，gn为B先手，A获得胜利的概率 。fn-1 = gn-1时，双方都希望

13、投反面（都 希望下步自己先手）， fn = PR6*fn-1 + PR5*gn-1 gn = PR8*fn-1 + PR7*gn-1fn-1 p 0 且 i q 0我们可以递推求得子游戏任意状态的SG函 数值。用SG定理可以求得和游戏的任意状 态的SG函数值。思考题 如果多堆的nimk游戏，第2k次操作只能拿走偶 数标号堆的石子，第2k+1次操作只能拿奇数标 号堆的石子。问题要如何解决？如果例题1中的堆数扩展到m堆，问题要如何解 决。想出几个关于take&break模型的转化问题。（ ACM ICPC 2006 beijing a funny stone game是 个经典的此问题的转化）想出

14、几个关于staircase nim模型的转化问题。（ 如POI2006 Stage）A Funny Stone Game David 玩一个石子游戏。游戏中，有n堆石 子,被编号为0.n-1。两名玩家轮流取石子。 每一轮游戏，每名玩家选取3堆石子i, j, k (ij, j=k,且至少有一枚石子在第i堆石子中) ，从i中取出一枚石子，并向j，k中各放入一 枚石子(如果j=k则向k中放入2颗石子)。最 先不能取石子的人输。Game在1 m (1 m 109)的棋盘上放置了n (1 n 106)枚棋子，棋盘格子从左到右标号为1到m，每 个棋盘格子上最多能放置一枚棋子。两个棋手轮 流对棋子进行操作，每轮操作仅能对一枚棋子进 行一次移动。移动棋子的方法如下：如果要移动 格子i上的棋子，那么一次移动只能将棋子移动到 标号大于i的格子中标号最小的空闲格子。谁第一 个把任意一枚棋子移动到m号格子，谁就取得了 胜利。