本文共 4821 字,大约阅读时间需要 16 分钟。
尼姆博奕(Nimm Game):有三堆各若干个物品,两个人轮流从某一堆取任意多的 物品,规定每次至少取一个,多者不限,最后取光者得胜。
这种情况最有意思,它与二进制有密切关系,我们用(a,b,c)表示某种局势,首先(0,0,0)显然是奇异局势,无论谁面对奇异局势,都必然失败。第二种奇异局势是
(0,n,n),只要与对手拿走一样多的物品,最后都将导致(0,0,0)。仔细分析一下,(1,2,3)也是奇异局势,无论对手如何拿,接下来都可以变为(0,n,n)的情 形。计算机算法里面有一种叫做按位模2加,也叫做异或的运算,我们用符号(+)表示这种运算。这种运算和一般加法不同的一点是1+1=0。先看(1,2,3)的按位模2加的结
果:1 =二进制01
2 =二进制10 3 =二进制11 (+) ——————— 0 =二进制00 (注意不进位)对于奇异局势(0,n,n)也一样,结果也是0。
任何奇异局势(a,b,c)都有a(+)b(+)c =0。
如果我们面对的是一个非奇异局势(a,b,c),要如何变为奇异局势呢?假设 a < b< c,我们只要将 c 变为 a(+)b,即可,因为有如下的运算结果: a(+)b(+)(a(+)
b)=(a(+)a)(+)(b(+)b)=0(+)0=0。要将c 变为a(+)b,只要从 c中减去 c-(a(+)b)即可。 例1。(14,21,39),14(+)21=27,39-27=12,所以从39中拿走12个物体即可达 到奇异局势(14,21,27)。例2。(55,81,121),55(+)81=102,121-102=19,所以从121中拿走19个物品
就形成了奇异局势(55,81,102)。例3。(29,45,58),29(+)45=48,58-48=10,从58中拿走10个,变为(29,4
5,48)。例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)奇异局势 甲胜。
推荐HDOJ题目
看完上面的结论,就能顺利解决上面2道了
S-Nim
博弈算法入门小节 1536 1517 1907
小子最近迷途于博弈之中。。。感触颇深。 为了让大家能够在学习博弈的时候少走弯路,最重要的也是为了加深自己的影响,温故而知新,特发此贴与大家共勉。 学博弈先从概念开始: 特别推荐LCY老师的课件:博弈入门。 下载地址: 这个课件个人认为从博弈的基本思想,一直到解博弈的中心算法做了很好的诠释。但是特别要注意的是。课件后面一部分英语写的讲义是重中之重。小子英语很弱,在这困扰很久。现在为大家大概介绍一下。 主要是后继点和SG值的问题: SG值:一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。 后继点:也就是按照题目要求的走法(比如取石子可以取的数量,方法)能够走一步达到的那个点。 具体的有关SG值是怎么运用的希望大家自己多想想。 课件后面有一个1536的代码。可以放在后面做做 看到这里推荐大家做几道题:1846(最简单的博弈水题) 1847(求SG值)有了上面的知识接下来我们来看看组合博弈(n堆石子)
推荐大家看个资料: 博弈-取石子游戏(推荐等级五星级) 这里提出了一个奇异状态的问题。看了这篇文章你会发现异或运算在博弈中使用的妙处。当然这里指出的只是组合博弈中一种特殊情况。 王道还是对SG值的求解,但是知道这么一种思路无疑对思维的广度和深度扩展是很有帮助的。 ZZ博弈 这里介绍了组和博弈的两种大的类型,一种是最后取的是N状态一种是最后取的是P状态,两个状态的解题方法能看懂很有帮助。当然,能够把推导过程理解,吃透无疑是大牛级的做法~小子也佩服的紧~ 1536题推荐做做这题,这题前面提醒大家是一个求SG值的题目,题目前面是对异或运算运用在组合博弈问题中的很好的解释。当然题目本身是有所不同的。因为在这里面对取法有所要求。那么这样就回归到了解决博弈问题的王道算法——求SG值上。 有关运用求SG值的博弈题目有: 1850(也可基于奇异状态异或) 1848(中和的大斐波那契数列的典型求SG值题) 1517(个人认为有点猥琐的题目。。。。在此题上困扰很久。当然搞出来很开心。小子是用比较规矩的求SG值的方法求出来的,但是论坛有人对其推出来了规律,这里佩服一下,大家可以学习一下) 1079(更猥琐的题目,对新手要求较高,因为按传统方法需要比较细致的模拟加对边角状态的考虑,同样有人推出来了公式) 当你全部看完以上的东西。做完以上的题目的话。。。小子恭喜你~你博弈入门了~~~~ 这里小子告诉大家。博弈很强大。学习要耐心~谢谢 Current System Time : 2008-12-11 19:16:03ACM课作业:
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://wuzni.baihongyu.com/