希望有编程高手应战！_编程吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：197,258贴子：
希望有编程高手应战！收藏
快试试吧，可以对自己使用挽尊卡咯~◆◆
我编了个小程序，放上网几周了，都没有对手，希望有编程高手应战！ &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 玩一个小游戏&&&&&&&&&&&&&&&&&& 任意放三堆棋子，每堆约20-50个，两人比赛，轮流拿棋，每次只能拿任意一堆中任意几个或全部，谁拿到最后一个为胜，有谁愿和我比赛? 非常欢 迎！一般人每堆5-10都不行，有点水平的10-20，我用“剪枝”的方法可达30-80，如果再大，时间超过几十秒，太长。如果谁超过我，告诉我一声。我先举几个例子，1： 20 30 50 先者赢。第三堆拿掉40个，用时6秒。2： 13 43 20 先者赢，第2堆拿掉18个，用时1秒。3：13 7&&10 先者输，用时1秒以内。4:&& 31 52 85 先者赢第三堆拿掉42个，用时57秒。如果，先者赢的，拿对了，后者就成了先者输了。如果，先者赢的，拿错了，后 者就成了先者赢，但也必须拿对，否则机会又还给了对方。现在留几题，&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 1：幼儿题 1 5 7&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 2：小学题 2 6 9 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 3：中学题 3 5 10 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 4：大学题 4 10 20&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 5：硕士题 5 26 30 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 6：博士题 6 30 40&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 7：超人题 40 62 84 第七题用时2分28秒，其它都1秒以内。有谁超过我或知道谁超过我的话，请告诉我，我当众宣布认输！从此不发此贴！email1:&& email2:&&
编程交流中心,教您编程!达内it软件编程专家,培养更多高端it人才.达内美国上市公司,新的教学模式,国内好的教师团队,让学生轻松学习.
快试试吧，可以对自己使用挽尊卡咯~◆◆
怎么没人接招？
快试试吧，可以对自己使用挽尊卡咯~◆◆
还是没人接招。
快试试吧，可以对自己使用挽尊卡咯~◆◆
会编大型游戏吗
快试试吧，可以对自己使用挽尊卡咯~◆◆
没钱的工作谁会接？除非是傻蛋。
快试试吧，可以对自己使用挽尊卡咯~◆◆
回复：5楼是比赛，不是工作。对会的人来说，只是几十句语句的事，几分钟搞定。除非不懂。我就喜欢比赛的，不信？你出题我来解。
快试试吧，可以对自己使用挽尊卡咯~◆◆
回复：4楼没编过。看来你编过，那么为什么这样的小程序不试试呢？又不费多少时间，除非不会。
快试试吧，可以对自己使用挽尊卡咯~◆◆
还是没人会，这个吧看来太失败！
这里有答案。我想都不用想就做出来了。
快试试吧，可以对自己使用挽尊卡咯~◆◆
回复：9楼转到“人工智能”吧去了。在该吧中，说的很热闹，但也没有一个会的。所以我在“编程”吧中找找知音！
编程?学编程选java开发语言,零基础入学到精通120天,学编程高薪就业好选择编程?学什么开发语言前景好?来博为峰学编程语言开发,2-4个月精通!
这是一种中国的古老游戏，用两堆石子，由两个人玩，与“拈”(参见《数学乐园·茅塞顿开》第152题)类似．顾名思义，玩的人轮流由石子堆中捡石子(图1)．玩的人可以从一堆石子中捡取任意数目的石子，或是从两堆石子中分别捡取相同数目的石子．捡到最后一粒石子的人赢．&&&&&& 显然如果你要赢，就要避免某些局面，比方说不应该留给你的对手只有一堆石子或是数目相同的两堆石子．还有哪些其他局面是要避免的呢？&&&& 假设你面对第一堆只有一粒石子，而第二堆有两粒石子(1，2)的情况(图2)．&&&&&& 你将任一堆的石子数降至0，你的对手都会赢．唯一的另一种可能性是你从第二堆中捡去一粒石子，这时每一堆都只剩下一粒石子，所以你的对手还是会赢．&&&& 当然，如果是你设下这种局面，那么赢的人就是你了．这种情况可由下列局面演变而来：&&&& (1，n) 从第二堆中捡去(n－2)粒石子．&&&& (2，m)从第二堆中捡去(m－1)粒石子．&&&& (r，r+1) 从每一堆捡去(r－1)粒石子．&&&& 也就是说，你不能把此种组合留给对方；如果对方把这种组合留给你，你就能形成(2，1)或(1，2)的局面而获胜．&&&& 试研究其他可以取胜的局面．
游戏1l&&&& 有两个游戏者：A和B。l&&&& 有21颗石子。l&&&& 两人轮流取走石子，每次可取1、2或3颗。l&&&& A先取。l&&&& 取走最后一颗石子的人获胜，即没有石子可取的人算输。如果剩下1、2或3颗石子，那么接下来取的人就能获胜；如果剩下4颗，那么无论接下来的人怎么取，都会出现前面这种情况，所以接下来取的人一定会输；如果剩下5、6或7颗石子，那么接下来取的人只要使得剩下4颗石子，他就能获胜。0，4，8，12，……都是下一个取石子者的必败状态。现在有21颗石子，21除以4的余数是1，所以先走者有必胜的策略，他第一次只要取走1颗石子，以后每一次都保证剩下的石子是4的倍数就行了。什么是“平等组合游戏”？l&&&& 两人游戏。l&&&& 有一个状态集，而且通常是有限的。l&&&& 规定哪些状态转移是允许的。l&&&& 所有规定对于两人来说是一样的。l&&&& 两人轮流走步。l&&&& 有一个终止状态，到达终止状态后游戏即告终止。l&&&& 游戏可以在有限步内终止。P状态和N状态就像第一个游戏一样，状态0，4，8，……是刚才走步的人的必胜状态，我们称之为P状态；而1，2，3，5，6，7，……都是下一个走步的人的必胜状态，我们称之为N状态。我们可以从终止状态出发，推出每一个状态，指出它是P状态还是N状态。就拿第一个游戏举例：步骤一 将所有终止状态设为P状态。步骤二 将所有一步之内可以到达一个P状态的状态设为N状态。步骤三 如果一个状态，不管怎么走都只能走到N状态，那么就将这个状态设为P状态。步骤四 返回步骤二。如果能够走到P状态，就能获胜。因为安照上面的定义，对手不管如何选择，只可能走到N状态。接下来总存在一个P状态你可以走到。这样一直走到终止状态，你获胜。当然这里所说得都是指对于最后走步的人获胜的游戏。我们严格的来定义P状态和N状态l&&&& 所有的终止状态都是P状态；l&&&& 对于任何的N状态，肯定存在一种方式可以一步转到一个P状态；l&&&& 对于任何的P状态，不管怎么走步，都只能转到N状态。而对于最后走步的人失败的游戏，只要将所有终止状态改成N状态，然后开始倒推就可以了。当然，必胜状态是N状态。也就是说，如果想胜利，就希望面对N状态，转移到P状态。现在对游戏1略微扩展一下。有一个决策集S，S中的元素是正整数。游戏的规则大致与游戏1一样，只是现在每次可以取的石子数必须是S中的元素。如果S={1，2，3}，那么就是游戏1。大家分析一下，当S={1，3，4}的时候，哪些状态是P状态，哪些是N状态。我们发现P状态是{0，2，7，9，14，16，……}，N状态是{1，3，4，5，6，8，10，……}。规律是如果n除以7的余数是0或2，那么状态n就是P状态，否则就是N状态。如果游戏开始时，石子总数是100，那么这是一个P状态，也就是说后走的人有必胜策略。游戏2 Nim游戏有三堆石子，分别含有x1，x2和x3颗石子。两人轮流取石子，每次可以选择一堆，从这堆里取走任意多颗石子，但不能不取。取走最后一颗石子的人获胜。我们用三元组来表示状态，很明显(0, 0, 0)是唯一的终止状态，是P状态。先考虑只剩一堆有石子的情况(0, 0, x)，很明显这是，这些状态都是N状态。剩两堆的情况，如果两堆的石子数相等(0, x, x)，那么这些都是P状态。因为下一次走步的人一定会使得两堆石子不相等，再下一次可以使得两堆的石子数回到相等的状态，包括终止状态。如果两堆的石子数不相等，那么就是N状态。
三堆都非空的情况就复杂得多。我们可以得到(1, 1, 1)、(1, 1, 2)、(1, 1, 3)和(1, 2, 2)都是N状态，因为它们可以转变成(0, 1, 1)或(0, 2, 2)，它们都是P状态。(1, 2, 3)是P状态，因为不管怎么选择，下一次一定变到N状态。“Nim和”就是两个数二进制表示的不进位加法，也就是两个整数进行xor位运算。定义：两个数(xm…x0)2和(ym…y0)2，是(zm…z0)2，其中zi=(xi+yi) mod 2，0&=i&=m。例如，22和51的Nim和是37：整数关于Nim和（以后用“+”表示）满足交换律和结合律。有单位元0，因为0+x=x。任何两个相等的数之和是0，即x+x=0。有削去律，即如果x+y=x+z，那么y=z。因为，如果x+y=x+z，两边都加上x，得到x+x+y=x+x+z，即y=z。定理1：Nim游戏的一个状态(x1, x2, x3) 是P状态，当且仅当x1+x2+x3=0。考虑状态(13, 12, 8)。Nim和是9，不等于0，所以这是一个N状态。那么接下来应该怎么走，才能走到一个P状态呢？你可以从第一堆中取走9颗石子。或者你也可以从第二堆中取走7颗石子，等等。如果石子的堆数大于3，只要堆数是有限的，上面的定理仍然成立。即如果有n堆石子，状态(x1, x2, …, xn)是P状态的充要条件是x1+x2+…+xn=0。下面就来证明。我们用ρ表示所有Nim和为零的状态组成的集合；用п表示ρ的补集，即所有Nim和为正整数的状态组成的集合。让我们逐一检验P状态和N状态的定义。l&&&& 所有的终止状态都在ρ中。由于终止状态只有一个(0, 0, …, 0)，0+0+…+0=0。l&&&& 所有属于п的状态，一步之内一定可以走到ρ中的状态。找出Nim和最左端为1的那一列，然后任意选择一个这一列是1的堆，从这堆中取走若干颗石子，使得Nim和为0。这总是可以做到的，因为将那一列的1变成0，而它左边的列不用修改，这个数就肯定变小了。对于其他Nim和是1的列，只要将这个数相对列的0改成1，1改成0就可以了。l&&&& 所有属于ρ的状态，一定转变到п中的状态。任意一个P状态(x1, x2, …, xn)，不妨假设从第一堆中取出若干颗石子。如果存在x1’&x1，而(x1’, x2, …, xn)也是P状态。那么x1+x2+…+xn=0=x1’+x2+…+xn，根据前面讲的削去律，x1’=x1，与假设x1’&x1矛盾。所以(x1’, x2, …, xn)一定是N状态，属于п。通过上面的证明，你能得到从一个N状态走到P状态的方案数吗？而且这个数是奇数。那么，对于最后走步的人失败的Nim游戏，又怎么办呢？通常情况下，这类游戏比最后走步的人获胜的游戏难得多。但Nim游戏是个例外。我们来分析一下。P状态和N状态的定义不变，如果初始状态是N状态，先走者有必胜策略。当超过1颗石子的堆数大于1的时候，按照前面所讲的方法走。直到超过1颗石子的堆数等于1，这时将这堆石子全部取掉或剩1颗，保证非空（剩下1颗石子）的堆数为奇数。如果初始状态是N状态，按照策略，先走者不可能将“超过1颗石子的堆数等于1”的状态留给对方，因为这样的状态不可能是P状态。而且对方不可能在一步之内从“超过1颗石子的堆数大于1”的状态变到“超过1颗石子的堆数小于1”的状态。图游戏现在我们使用有向图来描述一个游戏，所有的状态用顶点表示，所有合法的移动用有向边表示。接下来我们会给出Sprague-Grundy函数（简称SG函数），它比起P状态和N状态，能够提供更多的信息。定义：用(X, F)来表示有向图G。X是顶点集，F是后继函数。设x是一个顶点，F(x)是一个集合，包含于X，任意一个元素y属于F(x)，表示从x出发到y有一条边。F(x)就是x的后继集合，也可看成从x出发的决策集。如果F(x)是空集，那么就表示x是终止状态。图游戏：一个两人游戏，在一个图G(X, F)上玩，指明一个顶点x0并按照下列的规则：
l&&&& A先走，从x0开始；l&&&& 两人轮流走步；l&&&& 从顶点x出发，只能走到顶点y，y属于F(x)；l&&&& 遇到终止状态，即不能走步，此人输。对于一个图，如果不管x0是哪个点，总存在一个n，使得从x0出发的任意一条路经的长度都不超过n，那么这个图就被称为是“递增有界”的。接下来主要讨论递增有界的图游戏。拿游戏1来举例，设有n颗石子。顶点集X={0, 1, 2, …, n}，F(0)是空集，F(1)={0}，F(2)={0, 1}，F(k)={k-3, k-2, k-1}，3&=k&=n。下图是n=10的情况。SG函数定义：对于一个递增有界的图G(X, F)来说，SG函数g，是定义在X上的函数，函数值是非负整数，使得用语言来描述就是：g(x)的值等于所有x的后继的SG函数中没有出现的最小非负整数。对于递增有界的图，SG函数是唯一的、有界的。所有的终止状态x，因为F(x)是空集，所以g(x)=0。给出下图的SG函数。例1给出游戏1的SG函数，看看有什么规律，与P状态和N状态有什么关系。x&&&& 0&&&& 1&&&& 2&&&& 3&&&& 4&&&& 5&&&& 6&&&& 7&&&& 8&&&& 9&&&& 10&&&& 11&&&& …g(x)&&&& 0&&&& 1&&&& 2&&&& 3&&&& 0&&&& 1&&&& 2&&&& 3&&&& 0&&&& 1&&&& 2&&&& 3&&&& …例2有一堆石子，设当前剩下n颗石子，这一步至少要取走n/2取上界颗。唯一的终止状态是剩0颗石子。给出SG函数，看看有什么规律。x&&&& 0&&&& 1&&&& 2&&&& 3&&&& 4&&&& 5&&&& 6&&&& 7&&&& 8&&&& 9&&&& 10&&&& 11&&&& 12&&&& …g(x)&&&& 0&&&& 1&&&& 2&&&& 2&&&& 3&&&& 3&&&& 3&&&& 3&&&& 4&&&& 4&&&& 4&&&& 4&&&& 4&&&& …根据例1的结果，我们猜测SG函数与P状态和N状态是有关的。如果g(x)=0，那么x就是P状态，否则x就是N状态。证明是很显然的，我们只要根据两者的定义，考虑以下三点：l&&&& 如果x是终止状态，那么g(x)=0。l&&&& 一个状态x，如果g(x)≠0，那么一定存在一个x的后继y，使得g(y)=0。l&&&& 一个状态x，如果g(x)=0，那么所有x的后继y，都有g(y)≠0。当然，SG函数还包含了其他的信息，这些信息在以后会用到。多个组合游戏的并给定若干个组合游戏，可以按照下面的规则将它们并成一个新的游戏。l&&&& 对每个游戏给定初始状态。
l&&&& 两人轮流走步，从A开始。l&&&& 每一轮，选择一个未到达终止状态的游戏，在这个游戏中按照规则走一步，其他游戏的状态不变。l&&&& 最后一个走步者获胜，即走完之后所有游戏都到达终止状态。我们称这个新的游戏为“多个组合游戏的并”。我们要来看如何用每一个游戏的SG函数来求这个新的组合游戏的SG函数。n个图游戏的并定义：有n个递增有界的图游戏G1(X1, F1)，……，Gn(Xn, Fn)。把它们合并成一个新的游戏G(X, F)，记为G=G1+G2+…+Gn。X是所有游戏顶点集的笛卡尔积，即X=X1*X2*…*Xn。也就是说，我们用n元组(x1, x2, …, xn)来表示G中的顶点x，其中xi属于Xi，对于所有的i。x的后继F(x)可以定义成：这样定义的新的游戏G，一定也是递增有界的。把每个游戏的界相加，就得到了新游戏的界。正如Nim游戏那样，如果堆数是1，那么非常简单；如果堆数是2，也很容易分析；但堆数如果大于2，就不是很明显了。所以即使每个图游戏都是很平凡的，n个图游戏的并也可能相当复杂。下面介绍的SG定理可以看成是定理1的一般化。定理2设G=G1+G2+…+Gn，Gi的SG函数是gi，i=1, 2, …, n。那么G的SG函数g(x1, x2, …, xn)=g1(x1)+g2(x2)+…+gn(xn)，加法表示Nim和，即不进位的二进制加法。证明：令x(x1, x2, …, xn)是X中任意一点，b= g1(x1)+g2(x2)+…+gn(xn)。根据SG函数的定义，我们要说明两点：（1）、对于任意的非负整数a(a&b)，一定存在一个x的后继y，使得g(y)=a。（2）、x的任意一个后继y，都有g(y)¹b。首先来说明（1）。设d=a+b（nim和），d的二进制表示有k位，则2k-1&=d&2k。d的第k位是1而且a&b，所以a的第k位是0，b的第k位是1。因为b= g1(x1)+g2(x2)+…+gn(xn)，所以至少存在一个分量的第k位是1，不妨设它就是g1(x1)。那么，就有d+g1(x1)&g1(x1)，也就存在从x1到x1’的一次走步，使得g1(x1’) =d+g1(x1)。那么g1(x1’)+g2(x2)+…+gn(xn)=d+g1(x1)+g2(x2)+…+gn(xn) = d+b=a。再说明（2）。反证法。不失一般性，假设后继的走步是从x1到x1’，又有g1(x1’)+g2(x2)+…+gn(xn) =g1(x1)+g2(x2)+…+gn(xn)。根据消去率，g1(x1’)=g1(x1)，这与SG函数的定义不符，假设不成立。例3、你每次可以从一堆石子中取走{1, 2, …, m}颗。对于1堆的问题，SG函数gm(x)=x mod (m+1)。如果考虑3个这样的游戏的并，第一个游戏m=3，有9颗石子；第二个游戏m=5，有10颗石子；第三个游戏m=7，有14颗石子。g(9,10,14)=g3(9)+g5(10)+g7(14)=1+4+6=3，是一个N状态。要取胜的话，下一次可以选择第三个游戏，取走1颗石子，使得g7(13)=5。那么，还有别的取法吗？var&& n,m,p,t,i:begin&& readln(n);&& t:=0;&& for i:=1 to n do begin&&&& readln(m,p);&&&& t:=t xor (p mod (m+1));&&&&&& if t=0 then writeln('P') else writeln('N');end.取走-分割游戏这种游戏允许取走某些东西，然后将原来的一个游戏分成若干个相同的游戏。例1、Lasker’s Nim游戏：每一轮允许两种操作之一。（1）从一堆石子中取走任意多个（2）将一堆数量不少于2的石子分成都不为空的两堆。分析：很明显，g(0)=0，g(1)=1。状态2的后继有0，1和（1，1），它们的SG函数值分别是0，1和0，所以g(2)=2。状态3的后继有0，1，2和（1，2），它们的SG函数值分别是0，1，2和3，所以g(3)=4。状态4的后继有0，1，2，3，（1，3）和（2，2），它们的SG函数值分别是0，1，2，4，5和0，所以g(4)=3。在推一些，我们得到：
我们推测：对于所有的k&=0，有g(4k+1)=4k+1；g(4k+2)=4k+2；g(4k+3)=4k+4；g(4k+4)=4k+3。请自行证明。假设游戏初始时有3堆，分别有2、5和7颗石子。三堆的SG函数值分别是2、5和8，它们的Nim和等于15。所以要走到P状态，就要使得第三堆的SG值变成7，可以将第三堆分成按1和6分成两堆。var&& g:array[0..100]&& b:array[0..100]&& n,i,j:begin&& readln(n);&& g[0]:=0;&& for i:=1 to n do begin&&&& fillchar(b,sizeof(b),false);&&&& for j:=0 to i-1 do b[g[j]]:=&&&& for j:=1 to i div 2 do b[g[j] xor g[i-j]]:=&&&& j:=0;&&&& while b[j] do inc(j);&&&& g[i]:=j;&&&& writeln(i,': ',j);&&&&end.PAS2人玩的游戏，一个p*1的棋盘和红、绿、蓝三种棋子，棋子的大小分别是c*1、z*1和n*1，每种颜色的棋子个数无限。两人轮流摆放棋子，规则是：棋子不得超出棋盘范围；棋子不能有任何部分重叠；如果哪个人没有棋子可放，即算输。判断先手是否有必胜策略。输入：第一行是正整数c、z和n，都不超过1000。第二行是m，表示棋盘种类。接下来的m行，每行一个正整数p。m和p都不超过1000。输出：对于每种棋盘输出一行，如果先手必胜输出1，否则输出2。样例输入1 5 13 1 5 6输出112var&& c:array[1..3]&& g,q:array[0..1000]&& b:array[0..1000]&& m,maxq,i,j,k:begin&& assign(input,'pas.in'); reset(input);&& assign(output,'pas.out'); rewrite(output);&& readln(c[1],c[2],c[3]);&& readln(m);&& maxq:=0;&& for i:=1 to m do begin&&&& read(q[i]);&&&& if q[i]&maxq then maxq:=q[i];&&&&&& g[0]:=0;&& for i:=1 to maxq do begin&&&& fillchar(b,sizeof(b),false);&&&& for j:=1 to 3 do&&&&&& for k:=0 to i-c[j] do b[g[k] xor g[i-c[j]-k]]:=&&&& j:=0;&&&& while b[j] do inc(j);&&&& g[i]:=j;&&&&&& for i:=1 to m do&&&& if g[q[i]]=0 then writeln(2) else writeln(1);&& close(input); close(output);end.
Nim取子游戏Nim取子游戏是由两个人面对若干堆硬币（或石子）进行的游戏。设有k&=1堆硬币，各堆分别含有N1，N2，……NK枚硬币。游戏的目的就是选择最后剩下的硬币。游戏法则如下：1．两个游戏人交替进行游戏（游戏人I和游戏人II）；2．当轮到每个游戏人取子时，选择这些堆中的一堆，并从所选的堆中取走至少一枚硬币（游戏人可以取走他所选堆中的全部硬币）；3．当所有的堆都变成空堆时，最后取子的游戏人即为胜者。这个游戏中的变量是堆数k和各堆的硬币数N1，N2，……Nk。对应的组合问题是，确定游戏人I获胜还是游戏人II获胜以及两个游戏人应该如何取子才能保证自己获胜（获胜策略）。为了进一步理解Nim取子游戏，我们考查某些特殊情况。如果游戏开始时只有一堆硬币，游戏人I则通过取走所有的硬币而获胜。现在设有2堆硬币，且硬币数量分别为N1和N2。游戏人取得胜利并不在于N1和N2的值具体是多少，而是取决于它们是否相等。设N1！=N2，游戏人I从大堆中取走的硬币使得两堆硬币数量相等，于是，游戏人I以后每次取子的数量与游戏人II相等而最终获胜。但是如果N1= N2，则：游戏人II只要按着游戏人I取子的数量在另一堆中取相等数量的硬币，最终获胜者将会是游戏人II。这样，两堆的取子获胜策略就已经找到了。现在我们如何从两堆的取子策略扩展到任意堆数中呢？首先来回忆一下，每个正整数都有对应的一个二进制数，例如：57(10) = ) ，即：57(10)=25+24+23+20。于是，我们可以认为每一堆硬币数由2的幂数的子堆组成。这样，含有57枚硬币大堆就能看成是分别由数量为25、24、23、20的各个子堆组成。现在考虑各大堆大小分别为N1，N2，……Nk的一般的Nim取子游戏。将每一个数Ni表示为其二进制数（数的位数相等，不等时在前面补0）：N1 = as…a1a0N2 = bs…b1b0…… Nk = ms…m1m0如果每一种大小的子堆的个数都是偶数，我们就称Nim取子游戏是平衡的，而对应位相加是偶数的称为平衡位，否则称为非平衡位。因此，Nim取子游戏是平衡的，当且仅当：as + bs + … + ms 是偶数……a1 + b1 + … + m1 是偶数a0 + b0 + … + m0是偶数于是，我们就能得出获胜策略：游戏人I能够在非平衡取子游戏中取胜，而游戏人II能够在平衡的取子游戏中取胜。我们以一个两堆硬币的Nim取子游戏作为试验。设游戏开始时游戏处于非平衡状态。这样，游戏人I就能通过一种取子方式使得他取子后留给游戏人II的是一个平衡状态下的游戏，接着无论游戏人II如何取子，再留给游戏人I的一定是一个非平衡状态游戏，如此反复进行，当游戏人II在最后一次平衡状态下取子后，游戏人I便能一次性取走所有的硬币而获胜。而如果游戏开始时游戏牌平衡状态，那根据上述方式取子，最终游戏人II能获胜。下面应用此获胜策略来考虑4-堆的Nim取子游戏。其中各堆的大小分别为7，9，12，15枚硬币。用二进制表示各数分别为：，。于是可得到如下一表：&&&&& 23 = 8&&&& 22 = 4&&&& 21 = 2&&&& 20 = 1大小为7的堆&&&& 0&&&& 1&&&& 1&&&& 1大小为9的堆&&&& 1&&&& 0&&&& 0&&&& 1大小为12的堆&&&& 1&&&& 1&&&& 0&&&& 0大小为15的堆&&&& 1&&&& 1&&&& 1&&&& 1由Nim取子游戏的平衡条件可知，此游戏是一个非平衡状态的取子游戏，因此，游戏人I在按获胜策略进行取子游戏下将一定能够取得最终的胜利。具体做法有多种，游戏人I可以从大小为12的堆中取走11枚硬币，使得游戏达到平衡（如下表），&&&&& 23 = 8&&&& 22 = 4&&&& 21 = 2&&&& 20 = 1大小为7的堆&&&& 0&&&& 1&&&& 1&&&& 1大小为9的堆&&&& 1&&&& 0&&&& 0&&&& 1大小为12的堆&&&& 0&&&& 0&&&& 0&&&& 1大小为15的堆&&&& 1&&&& 1&&&& 1&&&& 1之后，无论游戏人II如何取子，游戏人I在取子后仍使得游戏达到平衡。同样的道理，游戏人I也可以选择大小为9的堆并取走5枚硬币而剩下4枚，或者，游戏人I从大小为15的堆中取走13枚而留下2枚。归根结底，Nim取子游戏的关键在于游戏开始时游戏处于何种状态（平衡或非平衡）和第一个游戏人是否能够按照取子游戏的获胜策略来进行游戏。问题: 能否考虑3进制或其它进制?
继续考虑4-堆的Nim取子游戏。其中各堆的大小分别为7，9，12，15枚硬币。用三进制表示各数分别为：，。于是可得到如下一表：&&&&& 32 = 9&&&& 31 = 3&&&& 30 = 1大小为7的堆&&&& 0&&&& 2&&&& 1大小为9的堆&&&& 1&&&& 0&&&& 0大小为12的堆&&&& 1&&&& 1&&&& 0大小为15的堆&&&& 1&&&& 2&&&& 0
Nim取子游戏的变形Nim取子游戏：设有n堆石子，两个人轮流拿走一定数目的石子，要求每次至少拿一枚石子，每次拿走的石子必须属于同一堆。拿到最后一枚石子的获胜。假设在第i堆中有Ai枚石子，那么另Nim-Sum = A1 ^ A2 ^ ... ^ An。如果Nim-Sum为0，那么下一个要取石子的人（先手）必败，反之必胜。那么如果取到最后一个石子的人输呢？首先考虑最简单的情况：每个堆中只有一枚石子，那么显然谁能获胜与堆的数目有关：如果堆的数目为奇数，先手必败，如果是偶数，则必胜。如果只有一个堆中的石子数目大于1，先手必胜，因为如果此时有奇数个大小为1的堆，他可以把大于1的那个堆中的石子取完；如果有偶数个大小为1的堆，那么他可以把大于1的那个堆变为只包含一个石子的堆。这样后手将面对奇数个大小为1的堆。如果有两个或两个以上的堆中包含的石子数目大于1呢？由于两个人都不可能一下把多个石子数大于1的堆变为没有大于1的堆，所以肯定会有一个人拿玩石子后，只剩下一个大小大于1的堆，这时下一个要拿石子的人将获胜。那么怎样判断谁会面对只有一堆石子数目大于1的状态呢？可以发现，只有一堆石子数目大于1的时候，Nim-Sum肯定不为0，所以如果初始状态下的Nim-Sum为0，那么先手必败，否则先手必胜。证明的思路是：如果Nim-Sum为0，那么下一个人不论怎样拿，只要按照规则，一定会使Nim-Sum不为0；如果Nim-Sum不为0，下一个人一定有一种拿石子的方法可以让Nim-Sum变成0。写成程序（n表示堆数，n1表示大小为1的堆的数目，num[i]表示第i堆中的石子数）Solve (int n, int num[]) {&&&&&&&&& n1 = 0;&&&&&&&& for (i = 1; i &= i++) {&&&&&&&&&&&&&&&& if (num[i] & 1) n1++;&&&&&&&& }&&&&&&&& if (n1 == n) {&&&&&&&&&&&&&&&& if (n1 % 2 == 1) 先手败&&&&&&&&&&&&&&&& else&&&&&&&&&&&&&&&&&&& 先手胜&&&&&&&& }&&&&&&&& else if (n1 + 1 == n) 先手胜&&&&&&&& else {&&&&&&&&&&&&&&& Nim_Sum = 0;&&&&&&&&&&&&&&& for (i = 1; i &= i++) {&&&&&&&&&&&&&&&&&&&&&&&& Nim_Sum ^= num[i];&&&&&&&&&&&&&&& }&&&&&&&&&&&&&&&& if (Nim_Sum == 0) 先手败&&&&&&&&&&&&&&& else&&&&&&&&&&&&&&&&&&&&&&&& 先手胜}
快试试吧，可以对自己使用挽尊卡咯~◆◆
回复：18楼我题中从幼儿到超人，我觉得你是天人！不过你还是选一题试试如何？
快试试吧，可以对自己使用挽尊卡咯~◆◆
回复：18楼是你抄来的还是自己做的？看来是抄的！那就不一样了，“天人”称号取消！玩笑，别生气！
登录百度帐号推荐应用}