组合博弈 取石子游戏

博弈问题分析——取石子游戏实例解答

<1>小红是个游戏迷，他和小蓝一起玩拿石子游戏。游戏规则为2个人轮流拿石子。一次可以拿1颗或3颗，规定谁取到最后一颗石子谁就胜出。最后决定由小红先取。两人都是游戏高手，该赢的绝不会输(表示不会失误）。问在知道石子总数的情况下，怎样快速预测谁将会胜出。

分析：

小红和小蓝各取一次共有三种情况：

②共取走2颗石子(1,1)

② 共取走4颗石子(1,3)

③ 共取走6颗石子(3,3)

设方案①取了N1次，方案②取了N2次，方案③取了N3次后，还剩下K（k<6,否则可以再取几轮，导致剩余量<6）个石子。最后K的取值有三种情况：0，1，3。

这个要解释一下：剩下的石子个数总共有0,1,2,3,4,5几种可能，2可以再取一轮（1,1）剩下0，4可以再取一轮（1,3）或者两次（1,1）剩下0，5可以再取（1,1）、（1,3）等的组合剩下1或3个，所以综合是最终会剩下0、1、3三种可能。

设有石子S.则S=2*N1+4*N2+6*N3+K.其中2*N1+4*N2+6*N3=（1+1）*N1+（1+3）*N2+（3+3）*N3，说明取的过程为偶数次，所以剩下K时该最先取石子的人取。K=1，3则先取方胜。反之，另一方胜。又2*N1+4*N2+6*N3=2*（N1+2*N2+3*N3）为偶数，所以S的奇偶性取决于K，当K为偶数时，后取方胜，反之，先取方胜。

总结：计算时可以先对6取余，如果余数为0、2、4，则K为0（偶数，后取者胜），如果余数为1、3、5则K为1或3（奇数，先取者剩）。

<2>有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够取胜。

（一）巴什博奕（Bash Game）：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）* r+s，（r为任意自然数，s≤m），那么先取者要拿走s个物品，如果后取者拿走k（k≤m）个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。

总结：通过分析可知，设n=(m+1)*r+s(s<=m),如果s等于0，则后取者获胜！如果s 不等于0，则先取者胜利！

（二）威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤bk ，k=0，1，2，……，n）表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。

我们可以知道，后面的奇异局势可以通过一轮特殊的取法变为更低的奇异局势！

可以看出，a0=b0=0，ak是未在前面出现过的最小自然数，而bk= ak + k，奇异局

势有如下三条性质：

1.任何自然数都包含在一个且仅有一个奇异局势中。

由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而

bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 .所以性质1.成立。

2.任意操作都可将奇异局势变为非奇异局势。

事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。

3.采用适当的方法，可以将非奇异局势变为奇异局势。

假设面对的局势是（a，b），若b = a，则同时从两堆中取走a 个物体，就变为了奇异局势（0，0）；如果a = ak ，b > bk，那么，取走b - bk个物体，即变为奇异局势；如果a = ak ，b < bk ，则同时从两堆中拿走ak - ab - ak个物体，变为奇异局势（a b - a k，a b - a k+ b - a k）；如果a > ak ，b= ak + k，则从第一堆中拿走多余的数量a - ak 即可；如果a < ak ，b= ak + k，分两种情况，第一种，a=aj （j < k），从第二堆里面拿走b - bj 即可；第二种，a=bj （j < k），从第二堆里面拿走b - aj 即可。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。

那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：

ak =[k*（1+√5）/2]，bk= ak + k （k=0，1，2，……，n 方括号表示取整函数）奇妙的是其中出现了黄金分割数（1+√5）/2 = 1.618……，因此，由ak，bk组成的矩形近似为黄金矩形，由于2/（1+√5）=（√5-1）/2，可以先求出j=[a（√5-1）/2]，若a=[j*（1+√5）/2]，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，

bj+1 = aj+1+ j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。

总结：分析到此已经很明显，判断谁个能够胜利看是否是奇异矩阵就行了，如果是奇异矩阵，则后取者胜利，如果是非奇异矩阵，则先取者得胜！在判断是不是咸佐夫博弈的奇异局势的时候，比如两个数a,b，则可以首先交换是a

（三）尼姆博奕（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）即可。

总结：面对奇异局势，先取者必定输，如果是非奇异局势，则先取者赢！如果一个局势（a,b,c）有a(+)b(+)c==0,则是奇异局势，如果不是，则不是奇异局势！

三堆石子的结论同样也适用于n堆石子的情况！

取火柴的游戏

题目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易得。

总结：如果先手遇到s态，则先手必赢，如果遇到T态，必败！

接着来解决第二个问题。

定义：若一堆中仅有1根火柴，则被称为孤单堆。若大于1根，则称为充裕堆。

定义：我们设只有一根火柴的堆为单根堆,否则为充裕堆,充裕堆>=2的T用T2表示,全是单根堆的T用T0表示(没有T1这种状态，分析可知)

同样的充裕堆>=2的S态用S2表示,全为孤单堆的S（可知堆数必为奇数）态用S0表示,只有一堆充裕堆的用S1表示

孤单堆的根数异或只会影响二进制的最后一位，但充裕堆会影响高位（非最后一位）。一个充裕堆，高位必有一位不为0，则所有根数异或不为0。故不会是T态。

[定理5]：S0态，即仅有奇数个孤单堆（没有充裕堆），必败。T0态必胜。

证明：

S0态，其实就是每次只能取一根。每次第奇数根都由己取，第偶数根都由对方取，所以最后一根必己取。败。同理, T0态必胜#

[定理6]：S1态，只要方法正确，必胜。

证明：

若此时孤单堆堆数为奇数，把充裕堆取完；否则，取成只剩下一根（此时变成S0态，但是自己是后手）。这样，就变成奇数个孤单堆，由对方取。由定理5，对方必输。己必胜。 # [定理7]：S2态不可转一次变为T0态。

证明：

充裕堆数不可能一次由2变为0。得证。 #

[定理8]：S2态可一次转变为T2态。

证明：

由定理1，S态可转变为T态，又由定理7，S2态不可转一次变为T0态，所以转变的T态为T2态。 #

[定理9]：T2态，只能转变为S2态或S1态。

证明：

由定理2，T态必然变为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题目

https://www.doczj.com/doc/4d14341868.html,/showproblem.php?pid=1907

https://www.doczj.com/doc/4d14341868.html,/showproblem.php?pid=2509

看完上面的结论，就能顺利解决上面2道了

S-Nim

https://www.doczj.com/doc/4d14341868.html,/showproblem.php?pid=1536

https://www.doczj.com/doc/4d14341868.html,/showproblem.php?pid=1944

博弈算法入门小节 1536 1517 1907

小子最近迷途于博弈之中。。。感触颇深。

为了让大家能够在学习博弈的时候少走弯路，最重要的也是为了加深自己的影响，温故而知新，特发此贴与大家共勉。

学博弈先从概念开始：

特别推荐LCY老师的课件：博弈入门。

下载地址：https://www.doczj.com/doc/4d14341868.html,/forum/read.php?tid=6875

这个课件个人认为从博弈的基本思想，一直到解博弈的中心算法做了很好的诠释。但是特别要注意的是。课件后面一部分英语写的讲义是重中之重。小子英语很弱，在这困扰很久。现在为大家大概介绍一下。

主要是后继点和SG值的问题:

SG值：一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。后继点：也就是按照题目要求的走法（比如取石子可以取的数量，方法）能够走一步达到的那个点。

具体的有关SG值是怎么运用的希望大家自己多想想。

课件后面有一个1536的代码。可以放在后面做做

看到这里推荐大家做几道题：1846（最简单的博弈水题）

1847（求SG值）

有了上面的知识接下来我们来看看组合博弈（n堆石子）

推荐大家看个资料：

博弈-取石子游戏(推荐等级五星级)

https://www.doczj.com/doc/4d14341868.html,/forum/read.php?fid=20&tid=5748

https://www.doczj.com/doc/4d14341868.html,/netnode/blog/item/30932c2edc7384514fc226ea.html

这里提出了一个奇异状态的问题。看了这篇文章你会发现异或运算在博弈中使用的妙处。当然这里指出的只是组合博弈中一种特殊情况。

王道还是对SG值的求解，但是知道这么一种思路无疑对思维的广度和深度扩展是很有帮助的。

ZZ博弈

https://www.doczj.com/doc/4d14341868.html,/forum/read.php?fid=9&tid=10617

这里介绍了组和博弈的两种大的类型，一种是最后取的是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

https://www.doczj.com/doc/4d14341868.html,/forum/read.php?tid=11339&fpage=0&toread=&page=1

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(i=0;i

{

if(b-f<0)//b-f后继点

break;

if(sg[b-f]==-1)

{

sg[b-f]=mex(b-f);

}

a[sg[b-f]]=1;

}

for(i=0;i

if(!a)

{

return i;

}

}

int main()

{

int i,t,n,s,bead,j;

while(cin >> k,k)

{

for(i=0;i

{

cin >> f;

}

memset(sg,-1,sizeof(sg)); for(i=0;i

for(j=i+1;j

if(f>f[j])

{

f+=f[j];

f[j]=f-f[j];

f-=f[j];

}

sg[0]=0;

cin >> t;

while(t–)

{

cin >> n;

s=0;

while(n–)

{

cin >> bead;//该堆的成员个数

if(sg[bead]==-1)

sg[bead]=mex(bead);

s=s^sg[bead];

}

if(s==0)

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(i=2;i<10;p=0,i++);

for(i=1;i<7000;i++)

{

for(j=2,min=-1;j<10;j++)

if(min==-1||a[p[j]]*j

a=a[p[min]]*min;

min=a[p[min]]*min;

if(a>=5000000000)

break;

for(j=2;j<10;j++)

if(a[p[j]]*j==min)

p[j]++;

}//从小到大求出所有乘积

while(scanf(“%I64d”,&n)!=EOF)

{

for(i=0;i<7000;i++)

{

sg=0;

if(a>=n)

break;

}

for(j=i-1;a[j]*9>=n&&j>=0;j–)

sg[j]=1;

while(j>=0)

{

for(k=j+1;k=a[k];k++) if(a[k]%a[j]==0&&sg[k]==0)

{

sg[j]=1;

break;

}

j–;

}

puts(sg[0]?”Stan wi ns.”:”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(i=s=temp=0;i

{

cin >> x;

if(x>1) temp=1;

s^=x;

}

if((s&&temp)||(!s&&!temp))

cout << “John” << endl;

else

cout << “Brother” << endl;

}

return 0;

}

Sprague-Grundy Function-简称sg

Nim游戏;比如说：有n堆石子，每次可以从第1堆石子里取1颗、2颗或3颗，可以从第2堆石子里取奇数颗，可以从第3堆及以后石子里取任意颗……这时看上去问题复杂了很多，但相信你如果掌握了本节的内容，类似的千变万化的问题都是不成问题的。

现在我们来研究一个看上去似乎更为一般的游戏：给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。事实上，这个游戏可以认为是所有Impartial Combinatorial Games(公正的组合游戏)的抽象模型。也就是说，任何一个ICG都可以通过把每个局面(状态、局势)看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义Sprague-Garundy 函数。

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

对于一个给定的有向无环图，定义关于图的每个顶点x的Sprague-Garundy函数g如下：g(x)=mex{ g(y) | y是x的后继}。

来看一下SG函数的性质。首先：

○1所有的terminal position(末端位置) n所对应的顶点，也就是没有出边的顶点，其SG值为0，因为它的后继集合是空集。（所有终结点是必败点（P点））

○2然后对于一个g(x)=0的顶点x，它的所有后继y都满足g(y)!=0。（无论如何操作，从必败点（P点）都只能进入必胜点（N点））

○3对于一个g(x)!=0的顶点，必定存在一个后继y满足g(y)=0。（从任何必胜点（N点）操作，至少有一种方法可以进入必败点（P点））

以上这三句话表明，顶点x所代表的postion是P-position当且仅当g(x)=0（跟P-positioin/N-position的定义的那三句话是完全对应的）。我们通过计算有向无环图的每个顶点的SG值，就可以对每种局面找到必胜策略了。但SG函数的用途远没有这样简单。如果将有向图游戏变复杂一点，比如说，有向图上并不是只有一枚棋子，而是有n枚棋子，每次可以任选一颗进行移动，这时，怎样找到必胜策略呢？

让我们再来考虑一下顶点的SG值的意义。当g(x)=k时，表明对于任意一个0<=i

对于n个棋子，设它们对应的顶点的SG值分别为(a1,a2,...,an)，再设局面(a1,a2,...,an)时的Nim游戏的一种必胜策略是把ai变成k，那么原游戏的一种必胜策略就是把第i枚棋子移动到一个SG值为k的顶点。这听上去有点过于神奇——怎么绕了一圈又回到Nim游戏上了。

其实我们还是只要证明这种多棋子的有向图游戏的局面是P-position当且仅当所有棋子所在的位置的SG函数的异或为0。这个证明与上节的Bouton's Theorem几乎是完全相同的，只需要适当的改几个名词就行了。

刚才，我为了使问题看上去更容易一些，认为n枚棋子是在一个有向图上移动。但如果不是在一个有向图上，而是每个棋子在一个有向图上，每次可以任选一个棋子（也就是任选一个有向图）进行移动，这样也不会给结论带来任何变化。

所以我们可以定义有向图游戏的和(Sum of Graph Games)：设G1、G2、……、Gn是n 个有向图游戏，定义游戏G是G1、G2、……、Gn的和(Sum)，游戏G的移动规则是：任选一个子游戏Gi并移动上面的棋子。Sprague-Grundy Theorem就是：g(G)=g(G1)^g(G2)^...^g(Gn)。也就是说，游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。

再考虑在本文一开头的一句话：任何一个ICG都可以抽象成一个有向图游戏。所以“SG函数”和“游戏的和”的概念就不是局限于有向图游戏。我们给每个ICG的每个position定义SG值，也可以定义n个ICG的和。所以说当我们面对由n个游戏组合成的一个游戏时，只需对于每个游戏找出求它的每个局面的SG值的方法，就可以把这些SG值全部看成Nim的石子堆，然后依照找Nim的必胜策略的方法来找这个游戏的必胜策略了！

回到本文开头的问题。有n堆石子，每次可以从第1堆石子里取1颗、2颗或3颗，可以从第2堆石子里取奇数颗，可以从第3堆及以后石子里取任意颗……我们可以把它看作3个子游戏，第1个子游戏只有一堆石子，每次可以取1、2、3颗，很容易看出x颗石子的局面的SG 值是x%4（0 1 2 3 0 1 2 3 0 1 2 3分布）。第2个子游戏也是只有一堆石子，每次可以取奇数颗，经过简单的画图可以知道这个游戏有x颗石子时的SG值是x%2。第3个游戏有n-2堆石子，就是一个Nim游戏。对于原游戏的每个局面，把三个子游戏的SG值异或一下就得到了整个游戏的SG值，然后就可以根据这个SG值判断是否有必胜策略以及做出决策了。其实看作3个子游戏还是保守了些，干脆看作n个子游戏，其中第1、2个子游戏如上所述，第3个及以后的子游戏都是“1堆石子，每次取几颗都可以”，称为“任取石子游戏”，这个超简单的游戏有x颗石子的SG值显然就是x。其实，n堆石子的Nim游戏本身不就是n个“任取石子游戏”的和吗？

所以，对于我们来说，SG函数与“游戏的和”的概念不是让我们去组合、制造稀奇古怪的游戏，而是把遇到的看上去有些复杂的游戏试图分成若干个子游戏，对于每个比原游戏简化很多的子游戏找出它的SG函数，然后全部异或起来就得到了原游戏的SG函数，就可以解决原游戏了。

藏族民间儿童游戏完整版

藏族民间儿童游戏 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】

藏族民间儿童游戏 一、找牛犊 由一名最小的孩子充当牛犊，其余孩子手拉手把他围在中间，再由一名孩子扮找牛犊者。找牛犊者装出什么也没看见，冲着孩子们喊道：“喂，看见牛犊了吗?”“你的牛犊什么样子?”孩子们反问。“我的牛犊上身是金做的，下身是银做的……”“我们没有这样美的牛犊，只有一只全身是泥的脏牛犊。”孩于们喊道。当找牛犊的孩子找到牛犊后，他要走进孩子们手拉手搭成的一个个门洞，去赶小牛犊。他先走到一个门洞前说：“这门是什么做的?”孩子们答到：“是黄金做的，要金钥匙才能打开。”找牛犊的孩子没有金钥匙，只好去问下一道门。后面的门还有银子的、玛瑙的、珊瑚的等等。当找牛人问到最后一道门时，孩子们立刻放下手，挤在一起，所有的门都关了。最后扮演找牛犊的孩子装出气势汹汹的样子说道：“我要是变成一头老牛，你们的门能挡住我吗？”说完就朝人群中冲，这时别的孩子就拉紧手快速旋转起来。如果找牛犊孩子冲进圈子中抢走小牛犊，那他就胜利了，闯不进去，就得认输。 二、老虎捉羊 首先用游戏方法确定孩子们的角色，即一个闭上眼睛俯卧在地，其他小孩伸出食指放在他身上，另一个小孩用拳头敲着叠在一起的手指问：“虎，一二三四猜猜是什么?”趴在地上的小孩说：“羊”。于是手指叠在最上面的孩子即确定为“羊”。用同样的方法，确定两只“虎”、一个“猎人”、一只“狗”和数只“羊”，游戏即可开始。玩法是：“虎”追扑“羊”，追上后在“羊”头上拍一下，被捉的”羊”就成了“虎”，直到把”羊”捉尽，游戏便结束。

取子游戏博弈简单分析

一局游戏在两个游戏人之间如下交替进行：游戏从一空堆开始。当轮到一个游戏人时，他可以往堆中加进1，2，3或4枚硬币。往堆中加进第100枚硬币的游戏人为得胜者。确定在这局游戏中是游戏人A还是游戏人B能够确保取胜。取胜的策略是什么？ 在学术论坛有 博士家园，组合图论论坛 确保取足5个硬币即可 例题：两个人玩移火柴的游戏，桌子上有1000根火柴，每个人每次可以拿走1-7根火柴，拿走桌子上最后那根火柴的算输，问第一个人第一次要拿多少根火柴才能保证赢 7根。以后对方拿几根，你都要拿够凑足8根的数。1000根和8根性质是一样的。 从抢30到NIM游戏的取胜策略 （一）倒推法 抢30是我国民间的一个两人游戏，具有很强的对抗性和娱乐性。抢30游戏通常有两种玩法。 （1）两人从1开始轮流报数，每人每次可报一个数或两个连续的数，谁先报到30，谁就为胜方。 （2）两人从1开始轮流报数，每人每次可报一个数或两个连续的数，同时把两个人报出的所有数累加，谁先使这个累加数最先达到30，谁就为胜方。 解决最个问题的一般策略是用倒推法。 以（1）为例，要抢到30，必须抢到27；要抢到27，必须抢到24。如此倒推回去，可得到一系列关键数30、27、24、21、18、……9、6、3。 根据以上分析，抢30游戏本身并不是一个公平的游戏，初始数和先后顺序已经决定了最后的结果，因为只有后报数者才能抢到3的倍数，后报数者有必胜策略。 （二）关键因子 所有这些关键数都是3的倍数。3是两个报数者年内能够报出的最大数与最小数的和。在类似游戏中，我们把游戏者所能用到的最大数和最小数之和称之为关键因子k，关键数就是k的倍数.。在抢30的游戏中，关键因子k等于3。 又例如，抢100报数游戏中，如果每人可报数为1至9个连续的自然数，谁先报到100谁就是胜利者。这里的关键因子k就是可报最大数9和可报最小数1的和，即k=10。

ACM竞赛试题集锦

取石子游戏 Time Limit:1S Memory Limit:1000K Total Submit:505 Accepted:90 Description 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。 Input 输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。 Output 输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。 Sample Input

2 1 8 4 4 7 Sample Output 1 跳蚤 Time Limit:1S Memory Limit:1000K Total Submit:198 Accepted:44 Description Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许

有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。 比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。 当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。 Input 两个整数N和M(N <= 15 , M <= 100000000)。 Output 可以完成任务的卡片数。 Sample Input

博弈之取石子经典游戏

由poj 1067引发的——取石子游戏【转自各类博弈】 (2011-07-25 23:46:54)[编辑][删除] 分类：编程道路~ 标签： 杂谈 上次做poj 1067的取石子游戏，只用到了whthoff博弈，未涉及到取石子的异或方法，今天重新搜索，整理了一遍。搜罗各种资料，加上自己整理，终于成篇啦！……噼里啪啦 取石子问题 有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够取胜。 （一）巴什博奕（Bash Game）：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。 显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。 即，若n=k*(m+1)，则后取着胜，反之，存在先取者获胜的取法。 n%(m+1)==0. 先取者必败。 这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。 从一堆100个石子中取石子，最后取完的胜。 （二）威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两 堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。 这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，...,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。 可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有 如下三条性质：

最新博弈游戏试题与答案

1．简述静态博弈和动态博弈的概念，并举例说明。（10分） 博弈双方没有信息交换下同时选择行动或是不同时行动，但双方不知道对方将会采取什么具体行动的博弈就是静态博弈。比如“囚徒困境”，双方不能交换信息，一方只能猜测推理对方会怎样做。博弈双方的行动有先后顺序，而且行动在后者可以观察到行动在先者的选择，并据此作出相应的选择，这种有信息交换的博弈就是动态博弈。比如说下棋，双方一先一后出棋，后一方可以看到前一方的行动，并据此来采取相应选择。 2．以“囚徒困境”说明什么是纳什均衡？（8分） 纳什均衡是指符合博弈双方个体理性最佳选择的惟一平衡点，在这点上，任何一人单方面改变选择都只会得到较差的结果。“囚徒困境”中，甲乙两名嫌疑犯，如果两人都坦白则各判8年；一人坦白一人不坦白，坦白的放出去，不坦白的判15年；如果两人都不坦白则各判15年。假设甲乙两人同样聪明，而且都只关心减少自己的刑期，不在乎对方。甲推理：假如乙不招供，他有两种选择○1招供—马上获得自由；○2不招供—坐牢1年。假设乙招供，他也有两种选择○1招供—坐牢8年；○2不招供—坐牢15年。由上可看出，不管乙招供不招供，甲选择招供都是对自己比较有利的。无论是甲，还是乙，他们均推理得出最好的策略是“招认”这是他们最符合个人理性的选择。双方均招认是“纳什均衡”——这是一个稳定的结果。此时甲乙任一方单方面改变选择都只会得到较差的结果。比如甲改变选择，不招供，他将获刑15年。 3．简述帕累托最优的概念，并举例说明（7分） 帕累托最优是指资源分配的一种状态，在不使任何人境况变坏的情况下，而不可能再使某些人的处境变好，即在这个状态下如果有人试图将自己的处境变好，就一定要有人的处境变坏，没有人能够在不顺还别人的利益的同时使自己的利益得到提高。比如一对热恋的情侣AB，他们的相恋是帕累托最优，此时第三者C追求A，AC相处更幸福，则A选择离开B，此时A失恋了，受到伤害。就是指在原来的帕累托最优的状态下，A试图将自己的处境变好，一定会让B的处境变坏。倘若第三者C追求A的同时，D追求B。且A、B都觉得此时比之前更幸福，则表明A、B相恋并未达到帕累托最优，仍存在改进，所以此时就没有人会受伤。

中国儿童民间传统游戏集

中国儿童民间传统游戏集 【导言】中国民间传统游戏在幼儿户外活动中有着悠久的历史和传统，流传下来的游戏项目也是数不胜数。它是一代又一代人传承下来的朴素智慧与生活趣味，也是那些物质匮乏年代，让小伙伴们乐此不疲亲密无间的嬉戏娱乐活动。传统的东西总是散发着永恒的味道，这些游戏不知道流传了多久，可是每一代孩童在玩耍的时候，趣味依旧。 1、骑马 玩法：三人一组，一人站立作马头，另一人在他背后双手搭他双肩弓身俯首作马身。第三人为骑马者，骑在作马身者的肩上。玩时三人同时口喊“嘿！嘿！嘿……”，数匹“马”竞相跑步向前，比谁跑得快。 2、坐轿 玩法：三人一组，两人抬轿一人坐轿。抬轿的两人各自把左手掌握在右手腕上，然后互相把右手握在对方左手腕上，形成一“井”字形。坐轿者双脚各插进抬轿者双手形成的环圈中，坐在手掌形成的“井”字上。玩时各组侧向疾跑，快者为胜。坐轿、抬轿者轮换担任。 3、骑竹马 玩法：以一支1．5米至2米长的竹竿作“竹马”，夹在骑者双腿间，左手握住竿的一端，另一端拖地，右手作持马鞭状。玩时口喊“嘿、嘿、嘿……”向前奔跑。多人玩时同时奔跑，快者为胜。 4、滚铁环 玩法：器具是一个水桶大小的铁环（旧时农村常用废旧水桶铁箍），一支1米左右小竹竿，竹竿一头插进以粗铁丝弯成的U字形弯钩。玩时手持竹竿一端，以另一端的U形铁弯钩推着铁环在地上滚动前进。多人玩时，看谁跑得快，且铁环不倒下。 5、踢鸡毛毽 玩法：鸡毛毽的制作简单，取一鸡翅膀上的粗羽毛，剪下一小截中间空的羽毛柄，往其空管中插进一束细鸡毛，再以布捆扎后固定在一个或两个铜钱中间的孔中，使鸡毛不至脱落即可。可一人以脚掌踢出各种花样，如踢至膝、肩、背、头等各部位；也可多人互相传递踢出各种花样。竞技时，以踢的数目多者为胜。 6、老鹰抓小鸡 玩法：一人扮老鹰，一人扮母鸡，其余人数不定，扮作小鸡。一“小鸡”在“母鸡”背后抓住“母鸡”衫尾，其余“小鸡”也都各牵住一人的后背衫尾，形成一列纵队。玩时，“老鹰”尽力设法要抓住“母鸡”后面的“小鸡”，扮“母鸡”的则张开双臂拦住“老鹰”，保护“小鸡”不被抓，众“小鸡”也在“母鸡”后面不断躲闪。若有“小鸡”被“老鹰”

四年级上游戏中的科学考级题目

四年级上游戏中的科学 考级题目 集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#

四年级（上）《游戏中的科学》考级题目 一、判断题（20题） 1．在做“会发出声音的绳子”这个游戏时，你会发现纽扣转得很快，并会扭转到相反方向。（ A ） A．对 B．错 2．水分子之间的距离要比空气分子之间的距离大。（ B ） A．对 B．错 3．声音不是靠声波振动进行传播的。（ B ） A．对 B．错 4．气球能将声音放大。（ A ） A．对 B．错 5．绳子的密度比空气大，因而传播效果比空气好。（ A ） A．对 B．错 6．在质量相同的情况下，热水的体积要比冷水小，密度却比冷水大。（ B ）A．对 B．错 7．“魔力气球”游戏中，套在瓶颈上的气球会变大是因为瓶子里的空气吸收了外部空气中的热量而膨胀，导致瓶子内部的空气体积变大。（ A ） A．对 B．错 8．白色能吸收所有的光。（ B ） A．对 B．错 9．打哈欠会“传染”，是因为在同一个房间里的人很可能都想睡觉了。（ B ）A．对 B．错 10．气球摩擦后不会吸水。（ B ） A．对 B．错 11.冷水溶化的冰糖和热水溶化的冰糖一样多。（ B ） A．对 B．错 12．我们把点燃的火柴放入蚊香的烟中，可以让烟消失。（ A ） A．对 B．错

13．将钉子加热烧成漆黑色后，把它放入装水的杯中，几分钟后，钉子还是漆黑色。（ B ） A．对 B．错 14．深色的物体对光与热的吸收力和浅色的物体一样。（ B ） A．对 B．错 15．昼夜交替现象是地球自传形成的，太阳并没有从空中升起或落下。（ A ）A．对 B．错 16．在晴朗的天气里，陆地和水中一样热。（ B ） A．对 B．错 17．花丛中的蝴蝶比草坪上的蝴蝶多。（ A ） A．对 B．错 18．蚂蚁不喜欢吃糖。（ B ） A．对 B．错 19．一个盘中，一半装深色的土，一半装淡色的沙，让灯照射这个盘子半小时，结果深色的土比浅色的沙温度要高许多。（ A ） A．对 B．错 20．铝锅不可以用来煎中药。（ A ） A．对 B．错 二、选择题（30题） 1. 在“会发出声音的绳子”这个游戏中，纽扣快速转动带动了（ A ）的振动，所以产生了“嗡嗡”声。 A．空气 B．手指 C．绳子 D．声音 2．一只吹气的气球和一只盛水的气球放在桌上，用手指弾扣桌面，用耳朵贴着两只气球仔细倾听弾扣声，你会发现（ B ）气球发出的声音比较清晰。 A．吹气的 B．盛水的 C．一样清晰 D．不能确定 3．唱歌时，喉咙里的（）产生振动，并通过（）传到玻璃纸上，使玻璃纸产生振动，从而带动芝麻跳起舞来。（ C ） A．声带嘴巴 B．舌头空气 C．声带空气

儿童民间传统游戏集

儿童民间传统游戏集 1、骑马 玩法：三人一组，一人站立作马头，另一人在他背后双手搭他双肩弓身俯首作马身。第三人为骑马者，骑在作马身者的肩上。玩时三人同时口喊“嘿！嘿！嘿……”，数匹“马”竞相跑步向前，比谁跑得快。 2、坐轿 玩法：三人一组，两人抬轿一人坐轿。抬轿的两人各自把左手掌握在右手腕上，然后互相把右手握在对方左手腕上，形成一“井”字形。坐轿者双脚各插进抬轿者双手形成的环圈中，坐在手掌形成的“井”字上。玩时各组侧向疾跑，快者为胜。坐轿、抬轿者轮换担任。 3、骑竹马 玩法：以一支1．5米至2米长的竹竿作“竹马”，夹在骑者双腿间，左手握住竿的一端，另一端拖地，右手作持马鞭状。玩时口喊“嘿、嘿、嘿……”向前奔跑。多人玩时同时奔跑，快者为胜。 4、滚铁环 玩法：器具是一个水桶大小的铁环（旧时农村常用废旧水桶铁箍），一支1米左右小竹竿，竹竿一头插进以粗铁丝弯成的U字形弯钩。玩时手持竹竿一端，以另一端的U形铁弯钩推着铁环在地上滚动前进。多人玩时，看谁跑得快，且铁环不倒下。 5、踢鸡毛毽 玩法：鸡毛毽的制作简单，取一鸡翅膀上的粗羽毛，剪下一小截中间空的羽毛柄，往其空管中插进一束细鸡毛，再以布捆扎后固定在一个或两个铜钱中间的孔中，使鸡毛不至脱落即可。可一人以脚掌踢出各种花样，如踢至膝、肩、背、头等各部位；也可多人互相传递踢出各种花样。竞技时，以踢的数目多者为胜。

6、老鹰抓小鸡 玩法：一人扮老鹰，一人扮母鸡，其余人数不定，扮作小鸡。一“小鸡”在“母鸡”背后抓住“母鸡”衫尾，其余“小鸡”也都各牵住一人的后背衫尾，形成一列纵队。玩时，“老鹰”尽力设法要抓住“母鸡”后面的“小鸡”，扮“母鸡”的则张开双臂拦住“老鹰”，保护“小鸡”不被抓，众“小鸡”也在“母鸡”后面不断躲闪。若有“小鸡”被“老鹰”的手摸到，便算被抓住，就得退场。达到一定时间后，“老鹰”抓到的“小鸡”超过“小鸡”数的一半，则“老鹰”胜；不到一半则“母鸡”胜。老鹰、母鸡、小鸡由游戏孩童抽签轮流担当。 7、抛沙包 玩法：器具是5个4厘米见方的布缝沙包。玩时，先把全部沙包放桌上（或地上），以右手先取一个往上抛，同时抓起桌上的一个沙包在掌心，再接住落下的沙包；然后再往上抛一个，同时抓起两个桌上的沙包，再接住落下的沙包。如此接着抓起三个桌上的沙包。第二遍玩时上抛两个沙包，第三遍三个沙包。接住下落的沙包时，若有沙包跌落为失败，则换另一人玩。往上抛沙包数多者胜。有的地方不用沙包而用小石子，称为“打五子”，玩法一样。 8、做屋 玩法：先在地上画一类似两个品字一个日字垒叠起来的2米长、1米宽的图形，每人持一小瓦片。玩时，一人先“做屋”，即以小瓦片丢在最面前的“日”字中的最前一格，然后以单腿自面前向远处格跳，每格只能落一只脚，横向两格的双脚同时落下，各踩一格，有瓦片的不能落脚，只能跨跳过去。一直跳到顶端时双脚落地，然后跳回到起步处，再把瓦片丢到第二格，照样跳到顶格转回来，再丢瓦片至第三第四格再跳，横向双格的丢瓦片顺序为先左后右。一直跳到瓦片丢到“天宫”返回后，便可做一座“屋”，即随意选上一格画上圈圈，算是属自己的“屋”，再跳时可双脚同时落在“屋”中，但对方的脚不能踩进此“屋”，得跨跳过去。若在跳的过程中踩线、或跌倒、或瓦片丢出界外，都属失败，应退出，改由对方跳。如此循环，做“屋”最多者为胜。

博弈论66个经典例子(9)不会令人后悔的纳什均衡

不会令人后悔的均衡 在纳什均衡中，你不一定满意其他的策略，但你的策略是回馈对手招数的最佳策略。 从囚徒困境中我们会发现，作为博弈各方的行动就是针对对方行动而确定的最佳对策，而一旦知道对方在做什么，就没人愿意改变自己的做法。博弈论学把这么一个结果称为均衡。这个概念是有普林斯顿大学数学家约翰·纳什提出的，因此被称为纳什均衡。 诺贝尔经济学奖获得者萨缪尔森有句名言，你可以将一只鹦鹉训练成经济学家，因为它所需要学习的只有两个词，供给与需求。博弈论专家坎多瑞引申说：“要成为现代经济学家，这只鹦鹉必须再多学一个词，这个词就是纳什均衡”。 1950年，还是一名研究生的纳什写了一篇论文，题为《n人博弈的均衡问题》，该文只有短短一页纸，可就这短短一页纸成了博弈论的经典文献。 纳什的贡献是，他证明了在这一类的竞争中，在很广泛的条件下是有稳定解存在的，只要是别人的行为确定下来，竞争者就可以有最佳的策略。 那么，什么纳什均衡呢？简单说，就是一策略组合中，所有的参与者面临这样的一种情况：给定你的策略，我的策略是我最好的策略。给定我的策略，你的策略也是你最好的策略，即双方在对方给定的策略下不愿意调整自己的策略。 纳什均衡从此成为经济学家用来分析商业竞争到贸易谈判现象的有力工具，所以纳什均衡是对冯诺依曼和摩根斯坦的合作博弈论的重大发展，甚至说是一场革命。 纳什均衡首先对亚当斯密“看不见的手”的原理提出挑战，按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果，

从纳什均衡引出一个悖论：从利己的目的触发，结果损人不利己。“囚徒困境”就是如此，从这个意义说，纳什均衡提出的悖论实际上动摇了西方经济学的基石。 纳什的想法成为我们指导“同时行动博弈”的最后一个法则的基础。这个法则如下：走完寻找优势策略和剔除劣势策略的捷径之后，下一步就是寻找这个博弈的均衡。所谓博弈均衡，它是一稳定的博弈结果。均衡是博弈的一结果，但不是说博弈的结果都能成为均衡。博弈的均衡是稳定的，因而是可以预测的。 在囚徒困境中存在唯一的纳什均衡点，即两个囚犯均选择“招认”，这是唯一稳定的结果。 有些博弈的纳什均衡点不止一个，如下述夫妻博弈中有两个纳什均衡点。 丈夫和妻子商量晚上的活动，丈夫喜欢看拳击，而妻子喜欢欣赏歌剧，但两个人都希望在一起度过夜晚。在这个夫妻博弈中有两个纳什均衡点：要么一同去看歌剧，要么一同去看拳击。在有两个或两个以上纳什均衡点的博弈中，其最后的结果难以预测。在夫妻博弈中，我们无法知道，最后结果是一同欣赏歌剧还是一同看拳击。 是不是所有的博弈均存在纳什均衡点呢？不一定存在纯策略纳什均衡点，但至少存在一个混合策略均衡点。 这里所谓纯策略是指参与者在他的策略空间中选取唯一确定的策略，所谓混合策略是指参与者采取的不是唯一的策略，而是其策略空间上的概率分布。 我们下面将在警察与小偷的博弈中给出混合策略的说明。 在西部片里，我们常能看到这样的故事：某个小镇上只有一名警察，他要负责整个镇的治安，现在我们假定，小镇的一头有一家酒馆，另一头有一家银行，再假定该地有一个小偷，要实施偷盗。因为分身乏术，警察一次只能在一个地方

取石子问题

取石子游戏 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 23080 Accepted: 7190 Description 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。 Input 输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。 Output 输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。 Sample Input 2 1 8 4 4 7 Sample Output 1 Source NOI 纠结了好久，也找同学玩了这个游戏，始终没发现什么规律。 后来想起高中一起玩（1，3，5，7）抓石子游戏的同学，就想打电话咨询顺便难一难他，谁知道直接拽给我一个：威佐夫博弈...百度了下终于懂了。 刚开始也想到列出前几种必胜组合，可是脑袋抽风了，（3，5）（5，3）算成两种情况。= =,我都搞不清楚当时怎么想的了。 下面是度娘关于威佐夫博弈的百科： 威佐夫博奕（Wythoff Game）： 有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，...,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而bk= ak + k。 奇异局势有如下三条性质：

几种两人轮流取石子游戏的输赢规律及取胜策略 续篇

几种两人轮流取石子游戏的输赢规律及取胜策略续篇上篇中第八种情况的推论有误，不能一概而论，因而第九种也有误。特此更正。 下面再看几种情况。分析的基础是上篇中的第四种情况。引用如下： 有三堆石子，个数分别是1、2、3个。 分析：若先取的把只有一个的一堆取完，则变成上篇中的第二种情况，后取的赢；若先取的从两个的一堆中取一个，则后取的把三个的一堆取完，变成第一种情况，后取的赢；若先取的把两个的一堆取完，变成上篇中的第二种情况，还是后取的赢。先取的从三个的一堆中取，不论取几个，用同样的方法进行分析，后取的都有办法赢。所以，先取的不论如何取法，后取的都有应对之策保证必赢。 一、有三堆石子，个数分别是1、3、4个。 分析：先取的只要从4个一堆中取出2个，就变成上篇中的第四种情况，所以先取的必赢。 二、有三堆石子，个数分别是1、4、5个。 分析：若先取的把只有一个的一堆取完，则变成上篇中的第二种情况，后取的赢；若先取的从4个的一堆中取一个，则后取的从5个的一堆中取3个，变成上篇中的第四种情况，后取的赢；其他情况不论先取的从4个或5个的一堆中取几个，后取的都有应对之策取胜；所以，后取的必赢。 三、有三堆石子，个数分别是1、5、6个。

分析：先取的只要从6个一堆中取出2个，就变成第二种情况，所以先取的必赢。 四、有三堆石子，个数分别是1、6、7个。 分析：若先取的把只有一个的一堆取完，则变成上篇中的第二种情况，后取的赢；若先取的从6个的一堆中取一个，则后取的从7个的一堆中取3个，变成第二种情况，后取的赢；其他情况不论先取的从6个或7个的一堆中取几个，后取的都有应对之策取胜；所以，后取的必赢。 五、有三堆石子，个数分别是1、7、8个。 分析：先取的只要从8个一堆中取出2个，就变成第四种情况，所以先取的必赢。 根据以上五种情况可以得出： 三堆石子中有一堆是1个，其他两堆的个数是相邻数的输赢规律及取胜策略是:石子个数在中间的数若是偶数，先取的必输，因为先取的不论怎么取都会使后取的有机会找到取后最终出现两堆石子个数相同的情况，所以先取的必输；石子个数在中间的数若是奇数，先取的必赢，因为先取的只要从个数最多的一堆中取出2个就变成上一种情况，所以先取的必赢。 再看三堆中石子个数最少的一堆是2个，其他两堆的个数是相邻数的情况。 六、有三堆石子，个数分别是2、3、4个。 分析：先取的只要从4个一堆中取出3个，就变成第四种情况，

七田真千幅图名称

七田真1000幅图中文名称 1青蛙2头巾3土星4煤5硫酸6水库7章鱼8牡蛎9吊床10热气球 11旗子12骸骨13鬼屋14通心粉15独眼怪物16照相机17海草18围巾19灯塔20影子 21萨克斯22百合23夏威夷24排球25哨子26水泥搅拌车27牡丹28年糕29被炉30长脖子怪物 31梅干32勺子33萤火虫34东京塔35黑板36粉笔37暗号38钱形平次39公园40杜鹃花 41铁锹42三角形43信44野猪45花瓶46复印机47丑女人48额头49梅50黄莺 51鳄鱼52摇篮53肥皂54霉55法院56和服57老鼠58琴59紧急出口60蜻蜓 61胸针62朋友63高尔夫球64鱼糕65电饭锅66蝙蝠67佐渡岛68力士69大鼓70牛蒡 71保龄球72推铅球73英国74桌子75毛衣76盂兰盆会舞77人造卫星78气球79歌手80合成器 81游泳池82丰臣秀吉83铜像84脚跟85黑痣86钥匙87田间小道88住宿车89门帘90洗衣机 91石油92炸薯条93番茄酱94围腰95圆木96枕头97毕加索98打呼噜99银杏100胡椒 101船长102选举103变色龙104拖把105演说106假牙107原始森林108算卦先生109放大镜110营火 111铁桶112麦克风113排气扇114电插座115蚯蚓116罐头117集会118拱廊119斗牛士120甜点 121走廊122芒草123月124冥想125积雨云126床单127拉链128幽灵129摔跤130女服务生 131盆132橙汁133芹菜134门松135牛仔136套环137大峡谷138飞艇139棉背心140狐狸 141钢琴142堤坝143新闻记者144传话筒145蟋蟀146厨房147罐子148漫画149盖子150砂糖 151熊猫152玻璃153过山车154月台155抽奖156草袋157胡同158金太郎159万岁160效游 161墨西哥162红辣椒163热狗164游览车(摩天轮)165婴儿166吹风机167豌豆168围裙169警察局170停车场 171青椒172羽毛球173膝盖174淋浴175切面176窗帘177面包店员178心型179饼180大使馆 181女王182记事本183涂画184垃圾箱185磁带186宫泽贤治187三角铃188执事189驼鸟190雪橇 191北斗七星192雾193口红194明信片195肥皂泡196小学校197太极拳198老头199量杯200理科实验室 201拿破仑202香水203音乐会204大号205茄子206啄木鸟207跳蚤208公寓209地板210井 211潜水镜212花坛213和尚214水管215蘑菇216剑术217八仙花（绣球花）218电影院219天线220火鸡 221风向标222龙卷风223鲆224鬣狗225毒药226石榴227乌龟228白雪公主229三色堇230日晷 231盒饭232蝴蝶结233机器人234柔道235心脏236螺丝钉237色拉油238人行道239士兵240帐本 241纸飞机242塑料简易温室243汽水244洪水245孙悟空246皮艇247墨鱼248算盘249大葱250煎蛋 251螃蟹252衣橱253炸肉饼254蒸汽火车255空间站256探照灯257亚洲大陆258干旱259弥猴桃260西装背心 261卖花姑娘262事务所263塞斯纳飞机264马达265降落伞266松树267章鱼焼268长颈鹿269编织(织毛衣)270贝雷帽271秃头海怪272悬崖273连环画剧274海豚275地层276奶酪277放射能278科学家279吸尘机280胶囊 281天鹅282乌鸦283口罩284隧道285书包286玉米287邮票288邮筒289爆玉米花290汽艇 291菲律宾292温泉293牛顿294头发295风筝296冰柱297赤道298失重299狐狸300猜拳 301护士302口风琴303蹦床304藤305镰刀306疣307雪人308竖琴309孔雀310商品目录 311电话312地毯313西班牙314管子315地铁316制服317鸡318图书馆319小丑320晾衣杆 321器皿(碟子)322咖喱饭323斧头324香蕉325蒲公英326货车327驾驶员328抽水马桶329加油站330眼镜 331火烈鸟332盐333瀑布334正方形335救生圈336蛋黄酱337菠菜338显微镜339龙虱340扳手(钳子) 341肘部342德国343山丘344袋鼠345滑雪346卧室(寝室)347百叶窗348猫头鹰349床350笔头菜

取石子游戏完全揭秘

由感性认识到理性认识 一、游戏 (2) 二、从简单入手 (2) 三、类比与联想 (6) 四、证明 (8) 五、推广 (11) 六、精华 (12) 七、结论 (16) 八、总结 (17)

一、游戏 游戏A： 甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如图1所示的初始局面：共n=3堆，其中第一堆的石子数a1=3，第二堆石子数a2=3，第三堆石子数a3=1。两人轮流按下列规则取走一些石子，游戏的规则如下： 每一步应取走至少一枚石子； 每一步只能从某一堆中取走部分或全部石子； 如果谁无法按规则取子，谁就是输家。 图 1 游戏的一个初始局面 游戏B： 甲乙双方事先约定一个数m，并且每次取石子的数目不能超过m个； 其余规则同游戏A。 我们关心的是，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。 下面，我们从简单入手，先来研究研究这个游戏的一些性质。 二、从简单入手 ?用一个n元组(a1, a2, …, a n)，来描述游戏过程中的一个局面。 ?可以用3元组(3, 3, 1)来描述图1所示的局面。

改变这个n元组中数的顺序，仍然代表同一个局面。 ?(3, 3, 1)和(1, 3, 3)，可以看作是同一个局面。 如果初始局面只有一堆石子，则甲有必胜策略。 甲可以一次把这一堆石子全部取完，这样乙就无石子可取了。 如果初始局面有两堆石子，而且这两堆石子的数目相等，则乙有必胜策略。 因为有两堆石子，所以甲无法一次取完； 如果甲在一堆中取若干石子，乙便在另一堆中取同样数目的石子； 根据对称性，在甲取了石子之后，乙总有石子可取； 石子总数一直在减少，最后必定是甲无石子可取。 ?对于初始局面(1)，甲有必胜策略，而初始局面(3, 3)，乙有必胜策略。 ?局面的加法：(a1, a2, …, a n) + (b1, b2, …, b m) = (a1, a2, …, a n, b1, b2, …, b m)。 ?(3) + (3) + (1) = (3, 3) + (1) = (3, 3, 1)。 ?对于局面A, B, S，若S=A+B，则称局面S可以分解为“子局面”A和B。 ?局面(3, 3, 1)可以分解为(3, 3)和(1)。 如果初始局面可以分成两个相同的“子局面”，则乙有必胜策略。 设初始局面S=A+A，想象有两个桌子，每个桌子上放一个A局面； 若甲在一个桌子中取石子，则乙在另一个桌子中对称的取石子； 根据对称性，在甲取了石子之后，乙总有石子可取； 石子总数一直在减少，最后必定是甲无石子可取。 ?初始局面(2, 2, 5, 5, 5, 5, 7, 7)，可以分成两个(2, 5, 5, 7)，故乙有必胜策略。

石头剪刀布游戏课程设计

课程设计说明书 课程名称：高级语言程序设计 设计题目：石头剪刀布游戏 院部：计算机科学与信息工程学院 学生姓名： 学号： 专业班级： 指导教师： 2014年6月

课程设计任务书

目录 一前言 (1) 二需求分析 (1) 三概要设计 (1) 四详细设计 (4) 五改进或增加功能模块说明 (5) 六程序测试 (6) 七课程设计总结 (7) 八致谢 (7) 九参考文献 (8) 十源程序 (8)

石头剪刀布游戏 一前言 传统的石头剪刀布游戏只是人和人之间进行的，双方只能一次出剪刀石头布三者之一，游戏的规则是石头>剪刀>布。现在是人和计算机出拳玩石头剪刀布游戏，规则相同，只不过需要对石头剪刀布进行字母代替，在程序中实现。最后比较输赢，统计成绩。 二需求分析 1 要求 （1）用C语言实现程序设计。 （2）定义各个函数分别完成不同功能，如设计，判断等。 （3）画出查询模块的流程图。 （4）界面友好（良好的人机互交），程序要有注释。 2 任务 （1）定义各类头文件，变量及宏定义。 （2）设定玩家操作模块和胜负判断模块。 （3）画出部分模块的流程图。 （4）编写代码。 （5）程序分析与调试。 3 运行环境 （1）WINDOWS2000/XP系统 （2）TurboC2.0编译环境 4 开发工具 系统描述语言C语言。 三概要设计 1 模块组成图

含有三个模块，人和电脑的输入，输入的比较计算，输出结果和评价。 图3-1 功能模块图 2 电脑随机输入流程图 现随机输入剪刀石头布，调用随机函数。 图3-2 功能模块图 3 用户输入流程图

对用户输入的数据进行判断是否是剪刀石头布或者是结果输出，判断用户的输入是否合法。 图3-3 功能模块图 4 计算比较流程图 对与用户和电脑输入的数据进行比较，判断用户的成绩，然后退出界面。 图3-4 功能模块图 四详细设计

小班科学活动：《石头碰碰乐》教学设计

小班科学活动：《石头碰碰乐》教学设计 Small class scientific activity: teaching design of "stone touching music"

小班科学活动：《石头碰碰乐》教学设计 前言：小泰温馨提醒，幼儿园是针对幼儿集中进行保育和教育的学前教育机构，幼儿不仅可以学到知识，从小接触集体生活，帮助孩子健康快乐地度过童年时光。幼儿园教育作为整个教育体系基础的基础，是对儿童进行预备教育，包括性格完整健康、行为习惯良好、初步的自然与社会常识。本教案是根据幼儿园小班儿童的学习特点、发展特点来设计并编辑成教学活动的内容。便于学习和使用，本文下载后内容可随意修改调整及打印。 目标 1、感知石头的基本特性，乐意参加玩石头的游戏，体验玩石头的乐趣。 2、尝试自由探索，发现硬的物体和石头碰撞可以产生响亮的声音，而软的物体与石头碰撞则没有声音，并愿意大胆表述。 准备： 1、物质准备：幼儿人手两块石头；若干件硬的物品（木头积木，金属勺子）；若干件软的物品（海绵，毛绒玩具）；厚垫子，桌子等，ppt图片。 2、经验准备：已学习节奏乐《闪烁的小星星》。 过程： 一、猜石头。（通过猜猜的游戏，激发兴趣） 1、师：今天小林老师带来了一位神秘的小客人就藏在这个袋子里，你们猜猜它是谁呢？ 2、师：听一听，有什么声音？（将包起来的石头放在地上敲）

3、请出石头朋友，问好。 师：想不想知道是什么东西呀？（原来是石头呀）小石头，你好呀！ 二、玩石头——“石头展览会”。（通过玩石头游戏，充分的体验石头的特性） 1、师：今天我们要去参观石头展览会，展览会上的石头想要和小朋友一起玩？去展览会有两个要求， 1、到展览会后可以选一个你喜欢的石头，每个小朋友只能选一个哦！记住了吗？ 2、就是拿到石头以后要赶快回到你的座位上，看一看石头是什么形状的？什么颜色的？石头上有什么？然后再用手摸一摸有什么感觉？也可以跟旁边的小朋友说一说你的发现。当你听到叮叮叮的声音，就赶紧把石头轻轻的放在椅子下，然后把小门关紧，要不然小石头就不跟你做朋友了。（引导幼儿闻一闻、摸一摸、再摸自己的脸，认识硬） 师：刚才小朋友都玩了石头，谁愿意来说说你的石头是什么形状的？（圆形、三角形、正方形、椭圆形）石头有什么颜色？（红色、白色、黑色、棕色）石头上有什么呀？（有的小朋友还发现石头上有花纹）石头摸上去有什么感觉呢？（硬硬的、冰冰的、粗糙的、光滑的） 小结：通过玩石头的游戏，知道石头有各种各样的形状和颜色，而不同的石头摸上去的感觉也不一样，有粗糙的，有光滑

一年级语文上册 捉迷藏教案2 鄂教版

捉迷藏 教学目标： 1.学会“下、见、石、你、比、同、个”7个生字，会认“迷、青、面、玩、吧、草、谁”7个生字。 2.正确、流利、有感情地朗读课文。（从标点符号和语气词入手，读出不同人物的语气。） 教学重点： 1.认识生字新笔画“竖提”、“横钩”。 2.学写生字，注意“比”字的笔顺。 3.正确流利地朗读课文。 4.读好人物的对话。 教学难点： 为什么三种小动物先提出玩不同的游戏，后来都同意玩捉迷藏？ 在教学过程中渗透识字方法的训练。 教学准备： 板书课题（加拼音，容易错的用红笔）；第一课时注意让学生明白什么是提示语，什么是人物说的话，多读小动物的话，配合着读；动物图片及头饰；教师投入心态：现场感；CAI字要重一些；多准备一些大吸铁石，吸住图片；教鞭；吸铁石梅花。 教学过程： 课前准备：现在冬天到了，在冬天里最不怕寒冷最不怕困难迎风雪开放、展示自己最美的一面的植物就是梅花。在这节课请你们学习梅花坚持的精神，就发给你一朵爱学习的小梅花。（评价学生会学习时用）。哪一大组学得好，就奖给哪一大组一朵大梅花。 （一）导入新课： （课前板书课题，将重点读音变成红色。贴课文重点图片。） 师：同学们，每个人都有童年，都喜欢和小伙伴们玩游戏。动物王国里也有三只小动物喜欢玩游戏。它们是谁啊？（课件出示：小青蛙、小鸭子、小兔子）今天我们继续学习第9课，学习它们怎样玩这个捉迷藏的故事。 齐读课题。 （二）游戏复习：

1．你们玩过捉迷藏游戏吗？让我们一起来玩捉迷藏游戏吧！上节课我们认识的生字朋友可调皮了，它们也和小动物们一起与我们玩起了捉迷藏的游戏，它们藏在了大树下不同的地方（学生读时，渗透藏的三个地方：一个大树洞里，一块大石头下面，一堆大草丛中）。当生字朋友露出小脑袋的时候，就请你们大声地把他叫出来，表示你们捉到了。听明白了吗？别着急，我知道你们很多人都想玩这个游戏，那这样吧，咱们开火车玩这个游戏。轮到你时，请你大声读，其他的同学用拍一次手的方式表示他找到了生字朋友。如果读得不对，老师请你们停下来，我再教教你，请你跟我学一学。开始：小火车，开起来，一开开到我这儿来！ 强调：吧，你，谁，吧，草 2．其他的同学也想捉迷藏吗？那咱们一起来捉捉吧！这一次，请你们读两次，表示你很肯定找到他了。听清楚了吗？ 3．这些生字朋友真会藏，你们也很会找。森林中的小青蛙、小鸭子、小兔子要考考大家了，看看你们会不会读这些词语。听清楚，每个词语读两次。如果有读得有问题的地方，老师做个停的手势请你们停下来，再教教你们。明白了吗？ 课件中加上：捉迷藏，两个，鸭子，石头，你们，游泳吧 4．同学们读得真准。小青蛙、小鸭子和小兔都为你们送上小星星，鼓励一下你们。 5．瞧，这三只小动物在大树下见面了！它们开心吗？（CAI出示三只小动物动画图）是啊，小青蛙开心地鼓起了腮帮唱起了歌，小鸭子摆着尾巴，好象很想游泳。小兔子也开心地扭起了屁股。让我们走进课文，来读读课文第一自然段吧！请翻开书89页。读书时，书斜立，身坐直。（评价：小梅花） 6．它们在哪儿开心地见面啦？（师贴图） （三）多种形式读人物对话，体会情感。 在学习中渗透认字方法：石比同个 1．猜猜，它们小脑袋凑在一起，在说些什么啊？指名说。（贴板书：商量） 2．它们是怎么商量的呢？请你们自由读一读课文2、3、4、5自然段（板书）划一划小动物商量时说的话吧！ 教师在巡视时，肯定学生边读边划。表扬读得清楚让老师也听得清楚的同学。（都要评价）3．谁来读你划的小青蛙的话？（课件出示青蛙话）（评价：小梅花）是这样划的同学请点点头。（课件中小青蛙呱呱地叫了，说你们真会学习啊！）这样，谁来把你划的小鸭子和小兔子的话读一读呢？（课件出示其他那两个小动物的话）相同的同学点点头。 4．你们就是这小青蛙、小鸭子和小兔子，咱们合作着读一读。老师读提示语，你们读小动物

Hdu中文题目

你HDOJ中文题目（第1部分） Start Time : 2013-11-07 11:07:00 End Time : 2013-12-04 11:07:00 Contest Status : Running Current System Time : 2013-11-08 23:20:28 Solved Problem ID Title Ratio(Accepted / Submitted) √1001 排序100.00%(1/1) √1002 武林0.00%(0/0) √1003 最小公倍数100.00%(2/2) √1004 敌兵布阵0.00%(0/0) √1005 猜数字0.00%(0/0) √1006 采矿0.00%(0/0) √1007 爆头0.00%(0/0) 1008 连连看0.00%(0/0) 1009 免费馅饼0.00%(0/0) 1010 诡异的楼梯0.00%(0/0) √1011 变形课0.00%(0/0) √1012 18岁生日0.00%(0/0) √1013 糖果大战0.00%(0/0) √1014 吃糖果0.00%(0/0) 1015 劲乐团0.00%(0/0) √1016 汉诺塔II0.00%(0/0) √1017 Eddy's 洗牌问题0.00%(0/0) 1018 圆桌会议0.00%(0/0) √1019 七夕节0.00%(0/0) 1020 超级密码0.00%(0/0) √1021 A + B0.00%(0/0) √1022 还是A+B100.00%(1/1) √1023 火星A+B0.00%(0/0) √1024 最大连续子序列0.00%(0/0) √1025 畅通工程0.00%(0/0) √1026 还是畅通工程0.00%(0/0)