7免费网站建站,民族建设集团有限公司官方网站,济南华企立方 网站,wordpress悬浮音乐播放以下是我从网上收集的关于组合博弈的资料汇总#xff1a; 有一种很有意思的游戏#xff0c;就是有物体若干堆#xff0c;可以是火柴棍或是围棋子等等均可。两个 人轮流从堆中取物体若干#xff0c;规定最后取光物体者取胜。这是我国民间很古老的一个游戏 #xff0c;别看这… 以下是我从网上收集的关于组合博弈的资料汇总 有一种很有意思的游戏就是有物体若干堆可以是火柴棍或是围棋子等等均可。两个 人轮流从堆中取物体若干规定最后取光物体者取胜。这是我国民间很古老的一个游戏 别看这游戏极其简单却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够 取胜。 一巴什博奕Bash Game只有一堆n个物品两个人轮流从这堆物品中取物规 定每次至少取一个最多取m个。最后取光者得胜。 显然如果nm1那么由于一次最多只能取m个所以无论先取者拿走多少个 后取者都能够一次拿走剩余的物品后者取胜。因此我们发现了如何取胜的法则如果 nm1rsr为任意自然数s≤m),那么先取者要拿走s个物品如果后取者拿走 k≤m)个那么先取者再拿走m1-k个结果剩下m1r-1个以后保持这样的 取法那么先取者肯定获胜。总之要保持给对手留下m1的倍数就能最后获胜。 这个游戏还可以有一种变相的玩法两个人轮流报数每次至少报一个最多报十 个谁能报到100者胜。 二威佐夫博奕Wythoff Game有两堆各若干个物品两个人轮流从某一堆或同 时从两堆中取同样多的物品规定每次至少取一个多者不限最后取光者得胜。 这种情况下是颇为复杂的。我们用akbkak ≤ bk ,k012…,n)表示 两堆物品的数量并称其为局势如果甲面对00那么甲已经输了这种局势我们 称为奇异局势。前几个奇异局势是00、12、35、47、6 10、813、915、1118、1220。 可以看出,a0b00,ak是未在前面出现过的最小自然数,而 bk ak k奇异局势有 如下三条性质 1。任何自然数都包含在一个且仅有一个奇异局势中。 由于ak是未在前面出现过的最小自然数所以有ak ak-1 而 bk ak k ak -1 k-1 bk-1 ak-1 。所以性质1。成立。 2。任意操作都可将奇异局势变为非奇异局势。 事实上若只改变奇异局势akbk的某一个分量那么另一个分量不可能在其 他奇异局势中所以必然是非奇异局势。如果使akbk的两个分量同时减少则由 于其差不变且不可能是其他奇异局势的差因此也是非奇异局势。 3。采用适当的方法可以将非奇异局势变为奇异局势。 假设面对的局势是a,b若 b a则同时从两堆中取走 a 个物体就变为了 奇异局势00如果a ak b bk那么取走b – bk个物体即变为奇异局 势如果 a ak b bk ,则同时从两堆中拿走 ak – ab – ak个物体,变为奇异局 势 ab – ak , ab – ak b – ak如果a ak b ak k,则从第一堆中拿走多余 的数量a – ak 即可如果a ak b ak k,分两种情况第一种aaj j k ,从第二堆里面拿走 b – bj 即可第二种abj j k,从第二堆里面拿走 b – a j 即可。 从如上性质可知两个人如果都采用正确操作那么面对非奇异局势先拿者必胜 反之则后拿者取胜。 那么任给一个局势ab怎样判断它是不是奇异局势呢我们有如下公式 ak [k1√5/2]bk ak k k012…,n 方括号表示取整函数) 奇妙的是其中出现了黄金分割数1√5/2 1。618…,因此,由akbk组成的矩形近 似为黄金矩形由于2/1√5√5-1/2可以先求出j[a√5-1/2]若a[ j1√5/2]那么a ajbj aj j若不等于那么a aj1bj1 aj1 j 1若都不是那么就不是奇异局势。然后再按照上述法则进行一定会遇到奇异 局势。 三尼姆博奕Nimm Game有三堆各若干个物品两个人轮流从某一堆取任意多的 物品规定每次至少取一个多者不限最后取光者得胜。 这种情况最有意思它与二进制有密切关系我们用abc表示某种局势首 先000显然是奇异局势无论谁面对奇异局势都必然失败。第二种奇异局势是 0nn只要与对手拿走一样多的物品最后都将导致000。仔细分析一 下123也是奇异局势无论对手如何拿接下来都可以变为0nn的情 形。 计算机算法里面有一种叫做按位模2加也叫做异或的运算我们用符号表示 这种运算。这种运算和一般加法不同的一点是110。先看123的按位模2加的结 果 1 二进制01 2 二进制10 3 二进制11 ——————— 0 二进制00 注意不进位 对于奇异局势0nn也一样结果也是0。 任何奇异局势abc都有abc 0。 如果我们面对的是一个非奇异局势abc要如何变为奇异局势呢假设 a b c,我们只要将 c 变为 ab,即可,因为有如下的运算结果: ab(a b)(aa)(bb)000。要将c 变为ab只要从 c中减去 c- ab即可。 例1。14213914212739-2712所以从39中拿走12个物体即可达 到奇异局势142127。 例2。55811215581102121-10219所以从121中拿走19个物品 就形成了奇异局势5581102。 例3。29455829454858-4810从58中拿走10个变为294 548。 例4。我们来实际进行一盘比赛看看 甲:(7,8,9)-(1,8,9)奇异局势 乙:(1,8,9)-(1,8,4) 甲:(1,8,4)-(1,5,4)奇异局势 乙:(1,5,4)-(1,4,4) 甲:(1,4,4)-(0,4,4)奇异局势 乙:(0,4,4)-(0,4,2) 甲:(0.4,2)-(0,2,2)奇异局势 乙:(0,2,2)-(0,2,1) 甲:(0,2,1)-(0,1,1)奇异局势 乙:(0,1,1)-(0,1,0) 甲:(0,1,0)-(0,0,0)奇异局势 甲胜。 取火柴的游戏 题目1今有若干堆火柴两人依次从中拿取规定每次只能从一堆中取若干根 可将一堆全取走但不可不取最后取完者为胜求必胜的方法。 题目2今有若干堆火柴两人依次从中拿取规定每次只能从一堆中取若干根 可将一堆全取走但不可不取最后取完者为负求必胜的方法。 嘿嘿这个游戏我早就见识过了。小时候用珠算玩这个游戏第一档拨一个第二档拨两个依次直到第五档拨五个。然后两个人就轮流再把棋子拨下来谁要是最后一个拨谁就赢。有一次暑假看见两个小孩子在玩这个游戏我就在想有没有一个定论呢。下面就来试着证明一下吧 先解决第一个问题吧。 定义若所有火柴数异或为0则该状态被称为利他态用字母T表示否则 为利己态用S表示。 [定理1]对于任何一个S态总能从一堆火柴中取出若干个使之成为T态。 证明 若有n堆火柴每堆火柴有A(i)根火柴数那么既然现在处于S态 c A(1) xor A(2) xor … xor A(n) 0; 把c表示成二进制记它的二进制数的最高位为第p位则必然存在一个A(t),它二进制的第p位也是1。否则若所有的A(i)的第p位都是0这与c的第p位就也为0矛盾。 那么我们把x A(t) xor c,则得到x A(t).这是因为既然A(t)的第p位与c的第p位同为1,那么x的第p位变为0,而高于p的位并没有改变。所以x A(t).而 A(1) xor A(2) xor … xor x xor … xor A(n) A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n) A(1) xor A(2) xor… xor A(n) xor A(1) xor A(2) xor … xor A(n) 0 这就是说从A(t)堆中取出 A(t) – x 根火柴后状态就会从S态变为T态。证毕 [定理2]T态取任何一堆的若干根都将成为S态。 证明用反证法试试。 若 c A(1) xor A(2) xor … xor A(i) xor … xor A(n) 0 c’ A(1) xor A(2) xor … xor A(i’) xor c xor … xor A(n) 0; 则有 c xor c’ A(1) xor A(2) xor … xor A(i) xor … xor A(n) xor A(1) xor A(2) xor … xor A(i’) xor c xor … xor A(n) A(i) xor A(i’) 0 进而推出A(i) A(i’)这与已知矛盾。所以命题得证。 [定理 3]S态只要方法正确必赢。 最终胜利即由S态转变为T态任何一个S态只要把它变为T态由定理1可以把它变成T态。对方只能把T态转变为S态(定理2)。这样所有S态向T态的转变都可以有己方控制对方只能被动地实现由T态转变为S态。故S态必赢。 [定理4]T态只要对方法正确必败。 由定理3易得。 接着来解决第二个问题。 定义若一堆中仅有1根火柴则被称为孤单堆。若大于1根则称为充裕堆。 定义T态中若充裕堆的堆数大于等于2则称为完全利他态用T2表示若充裕堆的堆数等于0则称为部分利他态用T0表示。 孤单堆的根数异或只会影响二进制的最后一位但充裕堆会影响高位非最后一位。一个充裕堆高位必有一位不为0则所有根数异或不为0。故不会是T态。 [定理5]S0态即仅有奇数个孤单堆必败。T0态必胜。 证明 S0态其实就是每次只能取一根。每次第奇数根都由己取第偶数根都由对 方取所以最后一根必己取。败。同理, T0态必胜# [定理6]S1态只要方法正确必胜。 证明 若此时孤单堆堆数为奇数把充裕堆取完否则取成一根。这样就变成奇数个孤单堆由对方取。由定理5对方必输。己必胜。 # [定理7]S2态不可转一次变为T0态。 证明 充裕堆数不可能一次由2变为0。得证。 # [定理8]S2态可一次转变为T2态。 证明 由定理1S态可转变为T态态可一次转变为T态又由定理6S2态不可转一次变为T0态所以转变的T态为T2态。 # [定理9]T2态只能转变为S2态或S1态。 证明 由定理2T态必然变为S态。由于充裕堆数不可能一次由2变为0所以此时的S态不可能为S0态。命题得证。 [定理10]S2态只要方法正确必胜. 证明 方法如下 1 S2态就把它变为T2态。由定理8 2 对方只能T2转变成S2态或S1态定理9 若转变为S2, 转向1 若转变为S1, 这己必胜。定理5 [定理11]T2态必输。 证明同10。 综上所述必输态有 T2,S0 必胜态 S2,S1,T0. 两题比较 第一题的全过程其实如下 S2-T2-S2-T2- …… -T2-S1-T0-S0-T0-……-S0-T0(全0) 第二题的全过程其实如下 S2-T2-S2-T2- …… -T2-S1-S0-T0-S0-……-S0-T0(全0) 下划线表示胜利一方的取法。 是否发现了他们的惊人相似之处。 我们不难发现(见加黑部分)S1态可以转变为S0态第二题做法也可以转变为 T0第一题做法。哪一方控制了S1态他即可以有办法使自己得到最后一根转变为 T0,也可以使对方得到最后一根转变为S0。 所以抢夺S1是制胜的关键 为此始终把T2态让给对方将使对方处于被动状态他早晚将把状态变为S1. 推荐HDOJ题目 http://acm.hdu.edu.cn/showproblem.php?pid1907 http://acm.hdu.edu.cn/showproblem.php?pid2509 看完上面的结论就能顺利解决上面2道了 S-Nim http://acm.hdu.edu.cn/showproblem.php?pid1536 http://acm.hdu.edu.cn/showproblem.php?pid1944 博弈算法入门小节 1536 1517 1907 小子最近迷途于博弈之中。。。感触颇深。 为了让大家能够在学习博弈的时候少走弯路最重要的也是为了加深自己的影响温故而知新特发此贴与大家共勉。 学博弈先从概念开始 特别推荐LCY老师的课件博弈入门。 下载地址http://acm.hdu.edu.cn/forum/read.php?tid6875 这个课件个人认为从博弈的基本思想一直到解博弈的中心算法做了很好的诠释。但是特别要注意的是。课件后面一部分英语写的讲义是重中之重。小子英语很弱在这困扰很久。现在为大家大概介绍一下。 主要是后继点和SG值的问题: SG值一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。 后继点也就是按照题目要求的走法比如取石子可以取的数量方法能够走一步达到的那个点。 具体的有关SG值是怎么运用的希望大家自己多想想。 课件后面有一个1536的代码。可以放在后面做做 看到这里推荐大家做几道题1846最简单的博弈水题 1847求SG值 有了上面的知识接下来我们来看看组合博弈n堆石子 推荐大家看个资料 博弈-取石子游戏(推荐等级五星级) http://acm.hdu.edu.cn/forum/read.php?fid20tid5748 http://hi.baidu.com/netnode/blog/item/30932c2edc7384514fc226ea.html 这里提出了一个奇异状态的问题。看了这篇文章你会发现异或运算在博弈中使用的妙处。当然这里指出的只是组合博弈中一种特殊情况。 王道还是对SG值的求解但是知道这么一种思路无疑对思维的广度和深度扩展是很有帮助的。 ZZ博弈 http://acm.hdu.edu.cn/forum/read.php?fid9tid10617 这里介绍了组和博弈的两种大的类型一种是最后取的是N状态一种是最后取的是P状态两个状态的解题方法能看懂很有帮助。当然能够把推导过程理解吃透无疑是大牛级的做法~小子也佩服的紧~ 1536题推荐做做这题这题前面提醒大家是一个求SG值的题目题目前面是对异或运算运用在组合博弈问题中的很好的解释。当然题目本身是有所不同的。因为在这里面对取法有所要求。那么这样就回归到了解决博弈问题的王道算法——求SG值上。 有关运用求SG值的博弈题目有 1850也可基于奇异状态异或 1848中和的大斐波那契数列的典型求SG值题 1517个人认为有点猥琐的题目。。。。在此题上困扰很久。当然搞出来很开心。小子是用比较规矩的求SG值的方法求出来的但是论坛有人对其推出来了规律这里佩服一下大家可以学习一下 1079更猥琐的题目对新手要求较高因为按传统方法需要比较细致的模拟加对边角状态的考虑同样有人推出来了公式 当你全部看完以上的东西。做完以上的题目的话。。。小子恭喜你~你博弈入门了~~~~ 这里小子告诉大家。博弈很强大。学习要耐心~谢谢 Current System Time : 2008-12-11 19:16:03 ACM课作业 1001 Brave Game 1002 Good Luck in CET-4 Everybody! 1003 Fibonacci again and again 1004 Rabbit and Grass 1005 Being a Good Boy in Spring Festival 1006 Public Sale 1007 悼念512汶川大地震遇难同胞——选拔志愿者 1008 kiki’s game 1009 Calendar Game 1010 A Multiplication Game 1011 Digital Deletions 1012 S-Nim http://acm.hdu.edu.cn/forum/read.php?tid11339fpage0toreadpage1 1536的参考代码 本部分设定了隐藏,您已回复过了,以下是隐藏的内容 Copy code //博弈-基于求SG值 //Accepted 1536 578MS 416K 904 B #include”iostream” using namespace std; int f[101],sg[10001],k; int mex(int b) { int a[101]{0},i; for(i0;ik;i) { if(b-f0)//b-f后继点 break; if(sg[b-f]-1) { sg[b-f]mex(b-f); } a[sg[b-f]]1; } for(i0;ik;i) if(!a) { return i; } } int main() { int i,t,n,s,bead,j; while(cin k,k) { for(i0;ik;i) { cin f; } memset(sg,-1,sizeof(sg)); for(i0;ik;i) for(ji1;jk;j) if(ff[j]) { ff[j]; f[j]f-f[j]; f-f[j]; } sg[0]0; cin t; while(t–) { cin n; s0; while(n–) { cin bead;//该堆的成员个数 if(sg[bead]-1) sg[bead]mex(bead); ss^sg[bead]; } if(s0) cout “L”; else cout “W”; } cout endl; } return 0; } 1517参考代码 本部分设定了隐藏,您已回复过了,以下是隐藏的内容 Copy code //博弈-基于求SG值 //Accepted 1517 234MS 0K 837 B #include”iostream” using namespace std; int main() { __int64 a[7000]{1},min,n; int p[10],sg[7000],i,j,k; for(i2;i10;p0,i); for(i1;i7000;i) { for(j2,min-1;j10;j) if(min-1||a[p[j]]*ja[p[min]]*min) minj; aa[p[min]]*min; mina[p[min]]*min; if(a5000000000) break; for(j2;j10;j) if(a[p[j]]*jmin) p[j]; }//从小到大求出所有乘积 while(scanf(“%I64d”,n)!EOF) { for(i0;i7000;i) { sg0; if(an) break; } for(ji-1;a[j]*9nj0;j–) sg[j]1; while(j0) { for(kj1;kia[j]*9a[k];k) if(a[k]%a[j]0sg[k]0) { sg[j]1; break; } j–; } puts(sg[0]?”Stan wins.”:”Ollie wins.”); } return 0; } 这里感谢shǎ崽同学的一段代码让小子学会了puts的妙用 1907参考代码 本部分设定了隐藏,您已回复过了,以下是隐藏的内容 #include”iostream” using namespace std; int main() { int temp,t,n,s,x,i; cin t; while(t–) { cin n; for(istemp0;in;i) { cin x; if(x1) temp1; s^x; } if((stemp)||(!s!temp)) cout “John” endl; else cout “Brother” endl; } return 0; }
