《简单的组合博弈游戏.pptx》由会员分享，可在线阅读，更多相关《简单的组合博弈游戏.pptx（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法与程序设计实训组合博弈游戏湖南涉外经济学院计算机科学与技术学部邹竞组合博弈游戏的概念和特点组合博弈游戏应满足以下性质：1.有两个游戏者。2.有一个可能的游戏状态集。这个状态集通常是有限的。3.游戏规则指定了在任何状态下双方的可能的走步和对应的后继状态集。如果在任意状态下双方的走步集合是相同的，那么说游戏是公平的(impartial)，否则是不公平的(partizan)。象棋是不公平的，因为每个人只能移动自己的子。4.两个游戏者轮流走步。5.当到达一个没有后继状态的状态后，游戏结束。在普通游戏规则(normalplayrule)下，最后一个走步的游戏者胜；在misere游戏规则下，最后一个走
2、步的游戏者输。如果游戏无限进行下去，我们认为双方打平，但通常我们会附加规定：6.不管双方怎么走步，游戏总能在有限步后结束。其他规则包括：不允许随机走步（不能扔色子或者随机洗牌），且必须信息完全的（如隐藏走步是不允许的），有限步结束时不能产生平局。在本节中，我们只考虑公平游戏，并且通常只考虑普通游戏规则（最后走步的胜）。和一般的双人零和博弈不同的是，这里的博弈游戏是特殊的：它们很好的数学特性，使得我们能够找到可判定输赢的数学策略，而不需要进行状态空间的搜索。P状态和N状态：假设双方都采取最明智的策略，则对于一些状态，刚完成走步的游戏者(PreviousPlayer)一定胜利，而对于其他状态，下一
3、个走步的游戏者(NextPlayer)一定胜利。把两种状态称为P状态(Pposition)和N状态(Nposition)，且有以下关系：1.所有终止状态是P状态2.能一步到达P状态的状态为N状态3.每一步都将到达N状态的状态为P状态我们也可以把P状态称为必败态，N状态称为必胜态，含义是直观的。以上关系实际上给出了一个递推计算所有状态的P-N标号的算法。只要状态集构成一个n个结点m条边的有向无环图(directedacyclicgraph,DAG)，则可以按照拓扑顺序在O(m)时间内计算所有状态的标号。可问题在于这样的状态往往有很多，能否通过数学方法直接判断一个状态是P状态还是N状态呢？常见的组
4、合博弈模型，有若干种，但也有很多情况，不能套用这些模型，要具体情况具体分析。博弈树模型假设甲乙双方在进行这种二人游戏，从唯一的一个初始局面开始，如果轮到甲方走棋，甲方有很多种着法，但只能选择一个着法进行走棋。甲方走棋后，局面发生了变化，轮到乙方走棋，乙方也有很多种着法，但也只能选择一个着法。从初始局面开始，甲乙两方交替走棋，局面的变化可以表示成一个树形结构，这就是博弈树（game-tree）。一种井字棋的博弈树，如图所示。每个局面可以用博弈树的一个结点来表示，某方获胜、失败或双方平局的结点构成了叶子结点。甲乙双方在选择着法时，不仅要考虑己方每一种着法的好坏，同时也要考虑对方会针对自己的每一种着
5、法采取怎样的着法来应对。显然，博弈树是一种特殊的与或树，“或”结点和“与”结点是逐层交替出现的。己方扩展的结点之间是“或”关系，对方扩展的结点之间是“与”关系。Bashs GameBashs Game（巴什博弈）（巴什博弈）所谓巴什博弈，是ACM题中最简单的组合游戏，大致上是这样的：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取1个，最多取m个，最后取光者得胜。显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=(m+1)*r+s，(r为任意自然数，sm)，即n%(m+1)!
6、=0，则先取者肯定获胜。巴什博弈还是很好理解的，以你是先手的角度考虑。你想把对手给弄垮，那么每一局，你都必须构建一个局势，这个局势就是每次都留给对手m+1的倍数个物品。因为，如果n=(m+1)r+s，(r为任意自然数，sm),那么先取者要拿走s个物品，如果后取者拿走k(m)个，那么先取者再拿走m+1-k个，结果剩下(m+1)(r-1)个,以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下(m+1)的倍数，就能最后获胜。这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报1个，最多报10个，谁能报到100者胜。好运！该死的英语四级！ProblemDescription大学英语四
7、级考试就要来临了，Kiki和Cici在紧张的复习之余喜欢打牌放松。“升级”？“斗地主”？那多俗啊！作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她们打牌的规则是这样的：1、总共n张牌；2、双方轮流抓牌；3、每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16）4、抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；假设Kiki和Cici都是足够聪明并且每次都是Kiki先抓牌，请问谁能赢呢？Input输入数据包含多个测试用例，每个测试用例占一行，包含一个整数n（1=n=1000）。Output若Kiki能赢的话输出“Kiki”，否则输出“Cici”，每个实例的输出占一行。Sa
8、mpleInput13SampleOutputKikiCici如果你是先手，考虑你的必胜态。注意，因为任何正整数都能写成若干个2的整数次方幂之和。由于规定只能取2的某个整数次方幂，只要你留给对手的牌数为3的倍数时，那么你就必赢，因为留下3的倍数时，对手有两种情况：1：如果轮到对方抓牌时只剩3张牌，对方要么取1张，要么取2张，剩下的你全取走，win！2：如果轮到对方抓牌时还剩3*k张牌，对手不管取多少，剩下的牌数是3*x+1或者3*x+2。轮到你时，你又可以构造一个3的倍数。所以无论哪种情况，当你留给对手为3*k的时候，你是必胜的。题目说Kiki先抓牌，那么当牌数为3的倍数时，Kiki就输了。否
9、则Kiki就能利用先手优势将留给对方的牌数变成3的倍数，就必胜。#includeusingnamespacestd;intmain()intN;while(cinN)puts(N%3!=0?Kiki:Cici);return0;土地拍卖ProblemDescription小鸡同学和鹏程同学始终没有逃过退学的命运，因为他们没有在程序设计竞赛中获奖，还为了争抢莎莎大打出手。现在等待他们的只能回家种田。要种田得有田才行，小鸡听说街上正在举行一场拍卖会，拍卖的物品正好就是一块田地。于是，小鸡带上他的全部积蓄，冲往拍卖会。后来发现，整个拍卖会只有小鸡和他的死对头鹏程。通过打听，小鸡知道这场拍卖的规则是这
10、样的：刚开始底价为0，两个人轮流开始加价，不过每次加价的幅度要在1N之间，当价格大于或等于田地的成本价M时，就把这块田地卖给这次叫价的人。小鸡和鹏程虽然比赛不行，但是对拍卖却十分精通，而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。由于抽签决定，所以每次都是由小鸡先开始加价，请问，第一次加价的时候，小鸡要出多少才能保证自己买得到这块地呢？Input本题目包含多组测试，请处理到文件结束(EOF)。每组测试占一行。每组测试包含两个整数M和N(含义见题目描述，0N，M1100)Output对于每组数据，在一行里按递增的顺序输出小鸡第一次可以加的价。两个数据之间用空格
11、隔开。如果小鸡在第一次无论如何出价都无法买到这块土地，就输出none。SampleInput423235SampleOutput1None345intmain()intn,m;while(scanf(%d%d,&m,&n)!=EOF)if(m%(n+1)=0)printf(nonen);continue;if(m=n)printf(%d,m);for(inti=m+1;i2时，(1,k)不是 P态，比如你要是面对(1,3)的局面，你是有可能赢的。同理，(k,2)，(1+k,2+k)也不是 P态，划去这些点以及它们的对称点，然后再找出 y=x上方剩余的点，你会发现(3,5)是一个 P态，如此下去
12、，如果我们只找出 ab的 P态，则它们是(0,0)，(1,2)，(3,5)，(4,7)，(6,10)它们有什么规律吗？忽略(0,0)，很快会发现对于第i个P态的a，a=i*(sqrt(5)+1)/2然后取整；而b=a+i。居然和黄金分割点扯上了关系。前几个必败点如下：(0,0)，(1,2)，(3,5)，(4,7)，(6,10)，(8,13)可以发现，对于第k个必败点(m(k),n(k)来说，m(k)是前面没有出现过的最小自然数，n(k)=m(k)+k。判断一个点是不是必败点的公式与黄金分割有关（我无法给出严格的数学证明，谁能给出严格的数学证明记得告诉我），为：m(k)=k*(1+sqrt(5)
13、/2n(k)=m(k)+k一个必败点有如下性质：性质1：所有自然数都会出现在一个必败点中，且仅会出现在一个必败点中；性质2：规则允许的任意操作可将必败点移动到必胜点；性质3：一定存在规则允许的某种操作可将必胜点移动到必败点；下面我们证明这3个性质。性质1：所有自然数都会出现在一个必败点中，且仅会出现在一个必败点中；证明：m(k)是前面没有出现过的最小自然数，自然与前k-1个必败点中的数字都不同；m(k)m(k-1)，否则违背m(k-1)的选择原则；n(k)=m(k)+km(k-1)+(k-1)=n(k-1)m(k-1)，因此n(k)比以往出现的任何数都大，即也没有出现过。又由于m(k)的选择原
14、则，所有自然数都会出现在某个必败点中。性质1证毕。性质2：规则允许的任意操作可将必败点移动到必胜点；证明：以必败点(m(k),n(k)为例。若只改变两个数中的一个，由于性质1，则得到的点一定是必胜点；若同时增加两个数，由于不能改变两数之差，又有n(k)-m(k)=k，故得到的点也一定是必胜点。性质2证毕。性质3：一定存在规则允许的某种操作可将必胜点移动到必败点；证明：以某个必胜点(i,j)为例，其中ji。因为所有自然数都会出现在某个必败点中，故要么i等于m(k)，要么j等于n(k)。若i=m(k)，jn(k)，可从j中取走j-n(k)个石子到达必败点；若i=m(k)，jn(k)，可从两堆同时拿
15、走m(k)-m(j-m(k)，注意此时j-m(k)n(k)-m(k)m(k)，j=n(k)，可从i中取走i-m(k)个石子到达必败点；若im(k)，j=n(k)，需要再分两种情况，因为i一定也出现在某个必败点中，若i=m(l)，则从j中拿走j-n(l)，若i=n(l)，则从j中拿走j-m(l)，从而到达必败点(m(l),n(l)。性质3证毕。移动的皇后ProblemDescription一个n*n棋盘上有一个皇后。每个人可以把它往左或下或左下45度移动任意多步。把皇后移动至左下角的游戏者获胜。现在给出皇后初始的X坐标和Y坐标，如果轮到你先走，假设双方都采取最好的策略，问最后你是胜者还是败者。I
16、nput输入包含若干行，表示若干种皇后的初始情况，其中每一行包含两个非负整数a和b，表示皇后的初始坐标，a和b都不大于1,000,000,000。Output输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。SampleInput218447SampleOutput010#includeusingnamespacestd;intmain()intm,n;while(cinmn)if(mn)inttemp;temp=m;m=n;n=temp;intk=n-m;intdata=floor(k*(1.0+sqrt(5.0)/2.0);if(data=m)cout00
17、)。参与游戏的两名玩家轮流执行这样的操作：清空一个盒子中的石子，然后从另一个盒子中拿若干石子到被清空的盒子中，使得最后两个盒子都不空。当两个盒子中都只有一枚石子时，游戏结束。最后成功执行操作的玩家获胜。找出游戏中所有的P位置。对于一个位置(x,y)来说，如果x,y中有一个偶数，那么(x,y)是N（必胜）位置。如果x和y都是奇数，那么(x,y)是P位置（必败）。可以用数学归纳法证明。证明（引自数学系唐思斯老师的证明）：证明结论：(x,y)至少一偶时，先手胜；都为奇时，先手败证明：(x,y)=(1,1)时是先手必败态下对max(x,y)1进行归纳1、当max(x,y)=2时，即(x,y)=(1,2
18、)或（2,1）或（2,2），先手留下一个2分为（1,1），先手获胜即当max(x,y)=2时结论成立。2、假设max(x,y)k时结论都成立，现证max(x,y)=k时结论成立若（x,y)中有一个偶数(设为a)，先手将另一个清空，把偶数a分为两个奇数b和c，由于b、ca小于等于 k，即max(b,c)k,由假设，在（b,c)位置上后手作为新先手必败，故先手胜若(x,y)都为奇数，先手只能保留一个奇数并将其分解为一奇a一偶b,由于max(a,b)max(x,y)=k,由假设，在（a,b)位置上后手作为新先手必胜，故先手败Chomp!博弈（巧克力游巧克力游戏戏）情人节的时候，潘典安买了一块长方形的
19、棋盘巧克力，和他最爱的女友一起吃，巧克力由n*m块格子组成。为了增加情人节的情趣，潘典安和她女友轮流选择一个格子，并把这个格子右面，上面和右上方的巧克力全部取走。取到左下角格子的玩家输，就要给对方一个热烈的吻。假设每次都是潘典安先手，他是否存在必胜策略呢？下图可以看作是一个3*8的巧克力被拿掉(6,2)和(3,2)两块后剩下的形状：答案是除了1*1的棋盘，对于其他大小的棋盘，先手总能赢。有一个很巧妙的证明可以保证先手存在必胜策略，可惜这个证明不是构造性的，也就是说没有给出先手怎么下才能赢。证明如下：如果后手能赢，也就是说后手有必胜策略，使得无论先手第一次取哪个石子，后手都能获得最后的胜利。那么
20、现在假设先手取最右上角的石子(n,m)，接下来后手通过某种取法使得自己进入必胜的局面。但事实上，先手在第一次取的时候就可以和后手这次取的一样，进入必胜局面了，与假设矛盾。Fibonaccis Game Fibonaccis Game（斐波那契博弈）（斐波那契博弈）斐波那契博弈模型，是ACM题中常见的组合游戏中的一种，大致上是这样的：有一堆个数为n的石子，游戏双方轮流取石子，满足：1.先手不能在第一次把所有的石子取完；2.之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。约定取走最后一个石子的人为赢家，求必败态。这个和之前的威佐夫博弈和取石子游戏有一个很
21、大的不同点，就是游戏规则的动态化。之前的规则中，每次可以取的石子的策略集合是基本固定的，但是这次有规则2：一方每次可以取的石子数依赖于对手刚才取的石子数。这个游戏叫做FibonacciNim，肯定和Fibonacci数列fn：1,2,3,5,8,13,21,34,55,89,有密切的关系。如果试验一番之后，可以猜测：先手胜当且仅当n不是Fibonacci数。换句话说，必败态构成Fibonacci数列。下面简单谈谈“先手败当且仅当n为Fibonacci数列”这一结论是怎么得来的。这里要用到一个很有用的定理：任何正整数可以表示为若干个不连续的Fibonacci数之和。这里定理涉及到数论，这里不做证
22、明，想要知道证明过程的请找你们数学老师。下面只谈如何把一个正整数表示为若干个不连续的Fibonacci数之和。比如，我们要分解83，注意到83被夹在55和89之间，于是把83可以写成83=55+28；然后再想办法分解28，28被夹在21和34之间，于是28=21+7；依此类推7=5+2，故83=55+21+5+2。如果n是Fibonacci数，比如n=89。89前面的两个Fibonacci数是34和55。如果先手第一次取的石子不小于34颗，那么一定后手赢，因为89-34=55=34+212*34，注意55是Fibonacci数。此时后手只要将剩下的全部取光即可，此时先手必败。故只需要考虑先手第
23、一次取得石子数fifj，如果fj 先手一开始所取石子数y的两倍，那么对后手就是面临x局面的先手，所以根据之前的分析，后手只要先取fj个即可，以后再按之前的分析就可保证必胜。下证：fj2y反证法：假设fj2y，则yfj/2=(fj-1+fj-2)/2fj-1。而最初的石子数是个斐波那契数，即n=fk=x+yfk-1+fi+fj+fj-1fk-1+fi+fi-1fk-1+fk-2fk（注意第一个不等号是严格的），矛盾！fj2y得证。如果n不是Fibonacci数，比如n=83，我们看看这个分解有什么指导意义：假如先手取2颗，那么后手无法取5颗或更多，而5是一个Fibonacci数，如果猜测正确的话
24、，（面临这5颗的先手实际上是整个游戏的后手）那么一定是整个游戏的先手取走这5颗石子中的最后一颗，而这个我们可以通过第二类归纳法来绕过，同样的道理，根据“先手败当且仅当n为Fibonacci数列”，接下去先手取走接下来的后21颗中的最后一颗，再取走后55颗中的最后一颗，那么先手赢。尼姆博弈尼姆博弈(Nimms Game)(Nimms Game)尼姆博弈模型，是ACM题中常见的组合游戏中的一种，大致上是这样的：有3堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取1个，多者不限，最后取光者得胜。这种情况最有意思，它与二进制有密切关系，我们用(a,b,c)表示某种局势，首先(0,0,0
25、)显然是必败态，无论谁面对(0,0,0)，都必然失败；第二种必败态是(0,n,n)，自己在某一堆拿走k（k n）个物品，不论k为多少，对方只要在另一堆拿走k个物品，最后自己都将面临(0,0,0)的局势，必败。仔细分析一下，(1,2,3)也是必败态，无论自己如何拿，接下来对手都可以把局势变为(0,n,n)的情形。计算机算法里面有一种叫做按位模2加，叫做异或的运算，我们用符号XOR表示这种运算，这种运算和一般加法不同的一点是1XOR1=0。先看(1,2,3)的按位模2加的结果：1=二进制012=二进制103=二进制11XOR0=二进制00(注意不进位)对于奇异局势(0,n,n)也一样，结果也是0。
26、任何奇异局势(a,b,c)都有aXORbXORc=0。如果我们面对的是一个非必败态(a,b,c)，要如何变为必败态呢？假设ab=0,nfory,y是x的后继形象的说就是X的g函数值为X的后继点的SG值中没有出现过的最小值。SG函数的性质：1、所有的终点（先手必败态），也就是没有出边的顶点，其SG值为0，因为它的后继集合是空集；2、对于一个g(x)=0的顶点x，它的所有后继y都满足g(y)!=0；3、对于一个g(x)!=0的顶点，必定存在一个后继y满足g(y)=0。下面将引入Sprague-Grundy定理，简称SG定理，并给上述的SG函数的性质进行证明。通过下面的定理可以建立SG函数与N局面和
27、P局面的关系：引引理：对于任意的局面理：对于任意的局面x，若，若g(x)=0则则x是是P局面局面（必败态）（必败态），否则，否则x是是N局面局面（必胜态）。（必胜态）。证明：我们对局面作数学归纳法：1.对于最终局面x，由定义x是P局面（必败态），而此时g(x)=0，引理成立。2.假设局面x的所有后继局面都满足引理。若x的后继局面中存在P局面（必败态）y，则x是N局面（必胜态），同时g(y)=0，故g(x)不等于0；若x的后继局面y中不存在P局面，则显然x是P局面；同时由于不存在g(y)=0，故g(x)=0。由归纳假设，引理对于所有局面x成立。我们通过计算有向无环图的每个顶点的SG值，就可以对每
28、种局面找到必胜策略了。实际中，SG函数的用途远没有这样简单。如果将有向图游戏变复杂一点，比如说，有向图上并不是只有一枚棋子，而是有n枚棋子，每次可以任选一颗进行移动，这时，怎样找到必胜策略呢？再来考虑一下顶点的SG值的意义。当g(x)=k时，表明对于任意一个0 i=0）。如果游戏者处在一个点x，g(x)=0。那么游戏者无论如何游戏者无论如何移动，下一个点的移动，下一个点的SG值都不等于值都不等于0。对于n个棋子，设它们对应的顶点的SG值分别为(a1,a2,.,an)，再设局面(a1,a2,.,an)时的Nim游戏的一种必胜策略是把某个ai变成k，那么原游戏的一种必胜策略就是把第i枚棋子移动到一
29、个SG值为k的顶点。这听上去有点过于神奇怎么绕了一圈又回到Nim游戏上了。可以用如下方式定义组合游戏的和：初始局面包含每个子游戏的初始局面，而每次每个游戏者可以任意选一个游戏，进行一次合法走步，而让其他游戏局面保持不变。3堆火柴的Nim游戏可以作看是3个一堆火柴的Nim游戏之和。一堆Nim游戏是简单的：直接把所有火柴拿掉即可；但3堆火柴却复杂得多。看样子，即使每个游戏都很简单，它们的和也可能很复杂。虽然看起来很复杂，但Sprague-Grundy定理提供了一个很好的方案解决这一问题：Sprague-Grundy定理定理：游戏和的SG函数等于各子游戏SG函数的Nim和，即：设gi(x)为Gi的S
30、G函数(1 i n)，则G=G1+G2+Gn的SG函数g(x1,x2,xn)=g1(x1)g2(x2)gn(xn)（其中为异或运算）。证明：对于G的任意局面x(x1,x2,xn，设b=g1(x1)g2(x2)gn(xn)，对于任意一个非负整数ab，如果我们能证明下面两个事实：（1）都存在x的一个后继局面y，使得g(y)=a；（2）不存在x的后继局面y，使得g(y)=b；则b就是满足要求的x的SG函数值，命题也就随之得证。对于事实1，令d=ab，设k是d的二进制位的最高位，即2k-1d2k。由于ab，故a的第k位为0，b的第k位为1。故g1(x1)、g2(x2)、gn(xn)中至少有一个二进制位
31、第k位为1，不妨设为g1(x1)，那么有dg1(x1)1时，对当前游戏者拿走k个球，还剩下r个球留给对方，r=n-k，其中1k(int)(n/2)，这样，r就有个范围，即int(n+1)/2)rn-1。博弈树是一种特殊的与或树，“或”结点和“与”结点是逐层交替出现的。己方扩展的结点之间是“或”关系，对方扩展的结点之间是“与”关系（关于博弈树的这段话关紧要，看不懂的同学可以掠过，看得懂的同学能在瞬间明白是怎么回事）。所以只要win(int(n+1)/2)、win(int(n+1)/2)+1)、win(int(n+1)/2)+2)、win(n-1)中所有的值是1，那么对方都必胜，自己就只能获得必败
32、态；但是，只要win(int(n+1)/2)、win(int(n+1)/2)+1)、win(int(n+1)/2)+2)、win(n-1)中存在某个值是0，那么自己可以获得必胜态。换句话来说：一旦发现某个r值使得win(r)=0，则从win(r+1)到win(2*r)的值都是1；一旦发现win(r+1)到win(2*r)的值都是1，则win(2*r+1)=0；上述分析很重要，搞明白上述分析后，r=1时，已知win(1)=0，能推出win(2)=1，以及win(3)=0。r=3时，由win(3)=0，又能推出win(4)=win(5)=win(6)=1，以及win(7)=0。r=7时，由win(
33、7)=0，又能推出win(8)=win(9)=.=win(14)=1，以及win(15)=0。r=15时，由于win(15)=0，又能推出win(16)=win(17)=.=win(30)=1，以及win(31)=0。r=31时，由于win(31)=0，又能推出win(32)=win(33)=.=win(62)=1，以及win(63)=0。自此，由数学归纳法可以证明，只有n=(int)pow(2,m)-1时（m为非负整数），win(n)=0，当前游戏者面临必败态，除此之外，当前选手都能面临必胜态！求win函数的代码我写了一个，只有寥寥数行。农大公布的标准程序采用的是递归的方法，我个人认为没有我
34、上面的算法效率高，我的算法实质上就是判断n+1是不是构成2的某个非负整数次方幂。猪县长同学写的程序可能效率更高，他采用的是预制表的办法，将问题规模内的2的所有整数次方幂-1的值放在一个向量或者数组中，然后用类似二分查找的办法去找，找到了就是先手必胜，否则先手必败。#includeusingnamespacestd;intWin(intn)intm=log(n+1)/log(2);intk=pow(2,m);if(k=n+1)return0;/先手必败 return1;/先手必胜intmain()intn;cinn;while(n0)if(Win(n)coutAlicen;elsecoutn;return0;