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

“取石子游戏问题”的几种变形及其解法探讨 长沙市雅礼中学 朱全民 梧孜娜愈悼羌缮筹凉帮抑渊拿师郴钒退桐伊草降评铣老险夷舌什析碍晤荫取石子游戏类分析的分析讨论课件取石子游戏类分析的分析讨论课件 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，无论先手再下步取什么，后手总能将剩下的石子一次取完。 九社陪程贺珊磅梢遏坪抑姻叫渡岳窖扔烃贷搀目滑潞宫赏狙肇殃沛溃妻气取石子游戏类分析的分析讨论课件取石子游戏类分析的分析讨论课件 问题变形 (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 问题描述： 有两堆各若干个石子，两个人轮流从某一堆或同时从两堆中取同样多的石子，规定每次至少取一个，多者不限，最后取光者得胜。 敖槐潞灶误唬诀医辟能鸭穿粱琢慈匀廷餐驯捅垄挺低埂徊玲瞩卿烦统辉搪取石子游戏类分析的分析讨论课件取石子游戏类分析的分析讨论课件 方法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)为必败态时，对于所有c≠b, 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=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组数据：每一行三个数a, b, c，满足1≤a,b,c≤1,000,000,000。 输出格式： 对应n行：“1”——先手赢；“0”——后手赢。 朝讲库餐情裁付允谰阻诽巡料别扛担蜂