一 : 由方仲永所想到的

有方仲永所想到的

今天，老师给我们上了方仲永这一课。

看完了这方仲永的事与老师的讲解，我顿时发出无限的感慨：天赋固难重要，但后天的教育却是更加不可缺少的，假入缺少了教育，就会如方仲永一样从神童到“泯然众人矣”连普通人都不如。

一个天资聪慧的神童五岁便能“指物做诗立就”却因为父母没文化以为带着方仲永四处拜访“有利可图”不让他学习，责任是在于父亲，但像方仲永这样的神童没经过后天努力都会变为普通人，那我呢？我天赋肯定不如方仲永，虽然我有良好的教育，但却没好好学。我越想越可怕：“假如我现在没好好学习，那以后我会成为什么呢？答案肯定是连普通人都不如。 所以现在我还在成长，就应该努力学习。长大后才能建设祖国，报答祖国，我想如果方仲永能生活在我们这个年代该多好啊！

我还记得这样的市里：牛顿虽不是神童，但他经过终身学习，终于取得成就。爱因斯坦也不是神童，大学还考了两次，毕业后去一家专利局当了七年的职员，还顽强学习，当了科学家。又如现在李天一，是个天子骄子，却因为父母过分溺爱，导致他前途尽毁。进了监狱。 这种种事例都表明了，神童努力就会有巨大的成就，但也可能如李天一，方仲永从天之骄子一落千丈，变为最为普通的普通人。但也可以如牛顿、爱因斯坦，不是神童却经过后天学习，拥有了世人瞩目的成就。、

最后下课后我知道了：不管天赋如何，无非就是起点高。只要肯付出，无论是不是神童总会有巨大的成就。又同意说明了一个道理：才能出自于勤奋学习，天赋不过是如跑步一般提前跑，只有学习才能成功。

二 : 由方仲永所想到的

在语文课上，我们学习了《伤仲永》。

《伤仲永》讲述“神童”方仲永变成了“泯然众人矣”的方仲永。

方仲永为什么会“泯然众人矣”？是天赋不够？还是另有原因？作者王安石说了：“卒之为众人，则其受于人者不至矣。”仲永的天赋是惊人的，因为五岁的他“未尝识书具”居然能“忽啼求之”而且“并书诗四句”并且“其文理皆有可观者”。于是“邑人奇之”。认为他长大一定能做大官。于是纷纷巴结他的父亲。于是仲永在这个时候，天赋正在磨灭。所以“泯然众人矣”。

我们大多数人不像他一样，五岁就“书诗四句”，有人字就写的歪歪扭扭的可我们从写字到作文，从数1和2到解方程，从“one，two”到“first，second”都是老师教的，就是“受于人”，我们没有仲永“受之天”的智慧，他也没我们“受于人”的教育。可有些同学课堂上说话，搞小动作，甚至在课堂上打的不分上下。他们总把学习推到明天，课堂作业，用他们的话说，是“借鉴”一下。当他们步入社会，就痛不欲生地教育孩子：“好好学习，别像我……”

究竟是谁毁了这颗“苗子”这全是方仲永的不是吗？不是。这一切是他的父亲一手造成的。他的父亲应该把他从到私塾里学习。不是“日扳仲永环谒邑人，不使学。”如果他的父亲让他去学习，仲永也许是太守，朝廷大臣，甚至是宰相。他的父亲就可(www.61k.com)以享受更多的荣华富贵了。只可惜他的父亲鼠目寸光，断送了仲永的的一生。

再把话题放到我们这个时代来。现在的父母基本知道知识的重要性。但有的父母目光短浅，因为九年制义务教育是免费的，有的家长等到孩子初中毕业，就给孩子找工作。让孩子仅凭他的初中知识来武装头脑。身强力壮的去扛东西，体弱的则当保姆，在她父母的店里计帐……当父母和儿子都失业以后，每天都数落孩子：“你看XX都上大学了，还是白领……”可这些家长想过没有：孩子为什么失业？是知识不高。孩子为什么知识不高？是你们让孩子们仅凭他的初中知识就去打工！当儿女没了工作，你没不自己反省一下，反而将怒气撒在儿女身上。他们失去学业和工作的痛苦已经够深了，这一句句的话，是在伤口上撒盐啊！为什么你们不让他们完成学业呢？

方仲永的悲剧告诉我们：后天的教育才是最重要的。

上蔡一中初一:赵辰阳

三 : 由高僧斗法所想到

由高僧斗法所想到…

摘要：这是博弈问题，组合数据，Nim游戏的变异，阶梯博弈的变种，高僧斗法。最重要三点：异或运行，奇数堆堆，必胜局

1. Nim游戏

桌面上有三行硬币，每一行中分别有a1、a2、a3个硬币，其中a1、a2、a3是可以任意指定的正整数。两个人轮流拿走硬币，每一次只能从某一行中拿走任意多个硬币，谁拿走最后一枚硬币谁就赢了。 Nim游戏（又名取石子问题）必胜策略可不是那么好想的。Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatori Games”（以下简称 ICG）。

德国的 nimm意思是“采取[必要]”或过时的英语动词NIM的含义相同。最早欧洲引用稔是从16世纪初，这个游戏很久以前就已经有了，可是必胜策略直至20世纪初才被哈佛大学的一个叫做Charles Leonard Bouton的数学家找到，可见其思维难度；可是，这个必胜策略却只要由一个运算就搞定了：Xor(异或)运算，可见Xor运算之神奇。

Xor运算的神奇性质之一，就是他自己是自己的逆运算，即对于任何两个布尔变量或者数有(a Xor b)Xor b=a。

void swap(int a, int b)

{a=a+b; b=a-b; a=a-b;}

void swap(int a, int b)//我们讲过！

{a=a^b; b=a^b; a=a^b;}

现在给你2n+1个正整数，其中有n对数和1个单独的数，（这里规定一对数的意思是这两个数相等），然后让你设计一种算法，把这个单独的数给找出来，要求时间复杂度为O(n)。比如说这2n+1个数是1 2 3 2 1，那么这个单独的数就是3。如果你的思路是依次挑出一个数然后和其余所有数比较一下看看是否相等，那就换个思路吧，因为这样的时间复杂度是O(n2)的。——1Xor2Xor3Xor2Xor1就一定是3了。就这么简单！

当硬盘的一个部分损坏之后可以推算出来损坏部分数据！

Xor的第二个神奇性质，是他满足消去率，即由a Xor c=b Xor c可以推出a=b，可以用上面一条性质轻松验证。

必败态。其严格定义如下：1.无法进行任何移动的局面是必败态；2.可以移动到必败态的局面是非必败态；3.在必败态做的所有操作的结果都是非必败态。这个还是很好理解的吧，就是自己处在非必败态上总能移动到必败态把必败态留给对方，而对方处在必败态的话总是只能移动到非必败态，把非必败态留给自己，然后自己继续虐对方。 而对于Nim游戏，局面是必败态当且仅当所有堆硬币的数量都异或起来结果为0，即a1^a2^...^an=0！！！为了证明之，我们只要证明它满足上述必败态的三条性质即可。 第一个命题显然，最终局面只有一个，就是全0，异或仍然是0。

第二个命题，对于某个局面(a1,a2,...,an)，若a1^a2^...^an!=0(不等号就用C++的习惯用!=来表示了)，一定存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。不妨设a1^a2^...^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定成立。则我们可以将ai改变成ai'=ai^k，此时a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。

第三个命题，对于某个局面(a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。因为异或运算满足消去率，由

a1^a2^...^an=a1^a2^...^ai'^...^an可以得到ai=ai'。所以将ai改变成ai'不是一个合法的移动。证毕。

#include <stdio.h>

void main()

{

int a,b[100],i,c;

scanf("%d",&a);

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

scanf("%d",&b[i]);

c=0;

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

{

c=c^b[i];//！！！！！！

}

if(c==0)

}

printf("后手赢/n"); else printf("先手赢/n");

先手的人如果想赢，可以有几种选择：

#include <stdio.h>

void main()

{

int a,b[100],i,c,d,h,j;

scanf("%d",&a);

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

scanf("%d",&b[i]);

d=0;

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

{

for(j=0;j<=b[i];j++)

{

c=b[i]-j;

h=0;

while(h<a)

{

} if(h!=i) { c=c^b[h]; } h++; } if(c==0) d++; } } printf("%d/n",d);

为了进一步理解Nim取子游戏，我们考查某些特殊情况。如果游戏开始时只有一堆硬币，游戏人I则通过取走所有的硬币而获胜。现在设有2堆硬币，且硬币数量分别为N1和N2。游戏人取得胜利并不在于N1和N2的值具体是多少，而是取决于它们是否相等。设N1！=N2，游戏人I从大堆中取走的硬币使得两堆硬币数量相等，于是，游戏人I以后每次取子的数量与游戏人II相等而最终获胜。但是如果N1= N2，则：游戏人II只要按着游戏人I取子的数量在另一堆中取相等数量的硬币，最终获胜者将会是游戏人II。这样，两堆的取子获胜策略就已经找到了。

现在我们如何从两堆的取子策略扩展到任意堆数中呢？

首先来回忆一下，每个正整数都有对应的一个二进制数，例如：57(10) ==111001(2) ，即：57(10)=25+24+23+20。于是，我们可以认为每一堆硬币数由2的幂数的子堆组成。这样，含有57枚硬币大堆就能看成是分别由数量为25、24、23、20的各个子堆组成。

现在考虑各大堆大小分别为N1，N2，……Nk的一般的Nim取子游戏。将每一个数Ni表示为其二进制数（数的位数相等，不等时在前面补0）：

N1 = as…a1a0

N2 = bs…b1b0

……

Nk = ms…m1m0

如果每一种大小的子堆的个数都是偶数，我们就称Nim取子游戏是平衡的，而对应位相加是偶数的称为平衡位，否则称为非平衡位。因此，Nim取子游戏是平衡的，当且仅当：

as + bs + … + ms 是偶数

……

归根结底，Nim取子游戏的关键在于游戏开始时游戏处于何种状态（平衡或非平衡）和第一个游戏人是否能够按照取子游戏的获胜策略来进行游戏。

http://blog.csdn.net/dinosoft/article/details/6795700 P-position和N-position

其中P 代表Previous，N 代表Next。 P-position是必败态，N-position是必胜态。 必败(必胜)点属性

(1) 所有终结点是必败点（P点）； //容易理解

(2) 从任何必胜点（N点）操作，至少有一种方法可以进入必败点（P点）； //就是那种我们要走的方法

(3)无论如何操作， 从必败点（P点）都只能进入必胜点（N点）. //对手走完又只能把N留给我们

取子游戏算法实现

步骤1:将所有终结位置标记为必败点（P点）；

步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）

步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ；

步骤4: 如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2 /*

上面的说法似乎不太好理解。我简单讲下。显然我们可以从终结条件递推回来。往后往前开始扫描，（终结状态方向为后）

a.如果当前是P点，那么一步（向前）可以走到的都是N点

b.如果当前点未标明P/N属性，那么看看该点向后走是不是都只能到达N点，如果是，那么该点是P点。

c.如果该点是N点，倒无法确定什么。

如果没办法标一个点，那么异常结束。

*/

2. 阶梯博弈

http://blog.csdn.net/kk303/article/details/6692506

阶梯博弈（staircase）游戏开始时有许多硬币任意分布在楼梯上，共n阶楼梯从地面由下向上编号为0到n。游戏者在每次操作时可以将楼梯j(1<=j<=n)上的任意多但至少一个硬币移动到楼梯j-1上。游戏者轮流操作，将最后一枚硬币移至地上的人获胜。 首先是对阶梯博弈的阐述...博弈在一列阶梯上进行...每个阶梯上放着自然数个点..两个人进行阶梯博弈...每一步则是将一个集体上的若干个点( >=1 )移到前面去..最后没有点可以移动的人输..

如这就是一个阶梯博弈的初始状态 2 1 3 2 4 ... 只能把后面的点往前面放...如何来分析这个问题呢...其实阶梯博弈经过转换可以变为Nim游戏。把所有奇数阶梯看成N堆石子..做nim..把石子从奇数堆移动到偶数堆可以理解为拿走石子..就相当于几个奇数堆的石子在做Nim..( 如所给样例..2^3^4=5 不为零所以先手必败)为什么可以这样来转化？ 假设我们是先手...所给的阶梯石子状态的奇数堆做Nim先手能必胜...我就按照能赢的步骤将奇数堆的石子移动到偶数堆...如果对手也是移动奇数堆..我们继续移动奇数堆..如果对手将偶数堆的石子移动到了奇数堆..那么我们紧接着将对手所移动的这么多石子从那个奇数堆移动到下面的偶数堆...两次操作后...相当于偶数堆的石子向下移动了几个..而奇数堆依然是原来的样子...即为必胜的状态...就算后手一直在移动偶数堆的石子到奇数堆..我们就一直跟着他将石子继续往下移..保持奇数堆不变...如此做下去..我可以跟着后手把偶数堆的石子移动到0..然后你就不能移动这些石子了...所以整个过程..将偶数堆移动到奇数堆不会影响奇数堆做Nim博弈的过程..整个过程可以抽象为奇数堆的Nim博弈...

其他的情况...先手必输的...类似推理...只要判断奇数堆做Nim博弈的情况即可... 为什么是只对奇数堆做Nim就可以...而不是偶数堆呢？...因为如果是对偶数堆做Nim...对手移动奇数堆的石子到偶数堆..我们跟着移动这些石子到下一个奇数堆...那么最后是对手把这些石子移动到了0..我们不能继续跟着移动...就只能去破坏原有的Nim而导致胜负关系的不确定...所以只要对奇数堆做Nim判断即可知道胜负情况...

3. 阶梯博弈变形

http://poj.org/problem?id=1704

/* 如上如图所示：排成直线的格子上有n个格子，棋子i在左数第pi个格子上。 G和B轮流选择一个棋子向左移动。每次移动可以移动一格及以上任意多个格， 但是不允许超其他的格子，也不允许将两个棋子放在同一个格子内。 无法移动就失败了。

转化： 如果将棋子两两看出一个整体考虑，我们就可以把这个游戏转为Nim游戏。先将棋子的个数的奇偶分情况讨论。

偶数：___1____5____8______10

就可以转化为

第一堆 5-1-1=3 个

第二堆 10-8-1=1 个。

为什么能这样转化？

考虑其中的一对棋子，将右边的棋子向左移动就相当于从Nim的石子堆中，取走石子 。 另一方面，将左边的棋子向左移动，石子的数量就增加了。这就与Nim不同。但是，即便对手增加了石子的数量，只要将所加部分减回去就回到了原来的状态；即便增加了石子的数量，只要对手将所加的部分减回去也就回到原来状态了。

偶数编号堆中的棋子个数不会影响局面的输赢状态。因为如果一个棋手将一些棋子从偶数编号堆移到奇数编号的堆中，那么他的对手总是可以将相同数目的棋子从这个奇数编号的堆中移动到编号更小的偶数编号堆中。移动偶数编号堆中的棋子并不会让对手无法移动。因此，一旦有棋子从奇数编号的堆中移动到偶数编号的堆中，那么这些棋子是不会影响局面的胜负状态的。

奇数：将最左边的0看出起始点就转化成偶数个了。

*/

#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int f[1003];

int main()

{

int T,n,i,k;

while(scanf("%d",&T)>0) {

}

while(T--) { } return 0; scanf("%d",&n); for(i=1;i<=n;i++) if(n%2==1) f[++n]=0; k=0; sort(f+1,f+1+n); for(i=n;i>=1;i=i-2) } k=k^(f[i]-f[i-1]-1); printf("Bob will win\n"); if(k==0) else printf("Georgia will win\n"); scanf("%d",&f[i]);

4. 高僧斗法

四 : 由高僧斗法所想到

由高僧斗法所想到…

摘要：这是博弈问题，组合数据，Nim游戏的变异，阶梯博弈的变种，高僧斗法。［www.61k.com］最重要三点：异或运行，奇数堆堆，必胜局

1. Nim游戏

桌面上有三行硬币，每一行中分别有a1、a2、a3个硬币，其中a1、a2、a3是可以任意指定的正整数。两个人轮流拿走硬币，每一次只能从某一行中拿走任意多个硬币，谁拿走最后一枚硬币谁就赢了。 Nim游戏（又名取石子问题）必胜策略可不是那么好想的。Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatori Games”（以下简称 ICG）。

德国的 nimm意思是“采取[必要]”或过时的英语动词NIM的含义相同。最早欧洲引用稔是从16世纪初，这个游戏很久以前就已经有了，可是必胜策略直至20世纪初才被哈佛大学的一个叫做Charles Leonard Bouton的数学家找到，可见其思维难度；可是，这个必胜策略却只要由一个运算就搞定了：Xor(异或)运算，可见Xor运算之神奇。

Xor运算的神奇性质之一，就是他自己是自己的逆运算，即对于任何两个布尔变量或者数有(a Xor b)Xor b=a。

void swap(int a, int b)

{a=a+b; b=a-b; a=a-b;}

void swap(int a, int b)//我们讲过！

{a=a^b; b=a^b; a=a^b;}

现在给你2n+1个正整数，其中有n对数和1个单独的数，（这里规定一对数的意思是这两个数相等），然后让你设计一种算法，把这个单独的数给找出来，要求时间复杂度为O(n)。比如说这2n+1个数是1 2 3 2 1，那么这个单独的数就是3。如果你的思路是依次挑出一个数然后和其余所有数比较一下看看是否相等，那就换个思路吧，因为这样的时间复杂度是O(n2)的。——1Xor2Xor3Xor2Xor1就一定是3了。就这么简单！

当硬盘的一个部分损坏之后可以推算出来损坏部分数据！

Xor的第二个神奇性质，是他满足消去率，即由a Xor c=b Xor c可以推出a=b，可以用上面一条性质轻松验证。

必败态。其严格定义如下：1.无法进行任何移动的局面是必败态；2.可以移动到必败态的局面是非必败态；3.在必败态做的所有操作的结果都是非必败态。这个还是很好理解的吧，就是自己处在非必败态上总能移动到必败态把必败态留给对方，而对方处在必败态的话总是只能移动到非必败态，把非必败态留给自己，然后自己继续虐对方。 而对于Nim游戏，局面是必败态当且仅当所有堆硬币的数量都异或起来结果为0，即a1^a2^...^an=0！！！为了证明之，我们只要证明它满足上述必败态的三条性质即可。 第一个命题显然，最终局面只有一个，就是全0，异或仍然是0。

斗法 由高僧斗法所想到

第二个命题，对于某个局面(a1,a2,...,an)，若a1^a2^...^an!=0(不等号就用C++的习惯用!=来表示了)，一定存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。（www.61k.com)不妨设a1^a2^...^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定成立。则我们可以将ai改变成ai'=ai^k，此时a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。

第三个命题，对于某个局面(a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。因为异或运算满足消去率，由

a1^a2^...^an=a1^a2^...^ai'^...^an可以得到ai=ai'。所以将ai改变成ai'不是一个合法的移动。证毕。

#include <stdio.h>

void main()

{

int a,b[100],i,c;

scanf("%d",&a);

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

scanf("%d",&b[i]);

c=0;

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

{

c=c^b[i];//！！！！！！

}

if(c==0)

}

printf("后手赢/n"); else printf("先手赢/n");

先手的人如果想赢，可以有几种选择：

#include <stdio.h>

void main()

{

int a,b[100],i,c,d,h,j;

scanf("%d",&a);

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

scanf("%d",&b[i]);

d=0;

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

{

for(j=0;j<=b[i];j++)

{

c=b[i]-j;

h=0;

while(h<a)

{

斗法 由高僧斗法所想到

} if(h!=i) { c=c^b[h]; } h++; } if(c==0) d++; } } printf("%d/n",d);

为了进一步理解Nim取子游戏，我们考查某些特殊情况。(www.61k.com］如果游戏开始时只有一堆硬币，游戏人I则通过取走所有的硬币而获胜。现在设有2堆硬币，且硬币数量分别为N1和N2。游戏人取得胜利并不在于N1和N2的值具体是多少，而是取决于它们是否相等。设N1！=N2，游戏人I从大堆中取走的硬币使得两堆硬币数量相等，于是，游戏人I以后每次取子的数量与游戏人II相等而最终获胜。但是如果N1= N2，则：游戏人II只要按着游戏人I取子的数量在另一堆中取相等数量的硬币，最终获胜者将会是游戏人II。这样，两堆的取子获胜策略就已经找到了。

现在我们如何从两堆的取子策略扩展到任意堆数中呢？

首先来回忆一下，每个正整数都有对应的一个二进制数，例如：57(10) ==111001(2) ，即：57(10)=25+24+23+20。于是，我们可以认为每一堆硬币数由2的幂数的子堆组成。这样，含有57枚硬币大堆就能看成是分别由数量为25、24、23、20的各个子堆组成。

现在考虑各大堆大小分别为N1，N2，……Nk的一般的Nim取子游戏。将每一个数Ni表示为其二进制数（数的位数相等，不等时在前面补0）：

N1 = as…a1a0

N2 = bs…b1b0

……

Nk = ms…m1m0

如果每一种大小的子堆的个数都是偶数，我们就称Nim取子游戏是平衡的，而对应位相加是偶数的称为平衡位，否则称为非平衡位。因此，Nim取子游戏是平衡的，当且仅当：

as + bs + … + ms 是偶数

……

斗法 由高僧斗法所想到

归根结底，Nim取子游戏的关键在于游戏开始时游戏处于何种状态（平衡或非平衡）和第一个游戏人是否能够按照取子游戏的获胜策略来进行游戏。[www.61k.com]

http://blog.csdn.net/dinosoft/article/details/6795700 P-position和N-position

斗法 由高僧斗法所想到

其中P 代表Previous，N 代表Next。［www.61k.com） P-position是必败态，N-position是必胜态。 必败(必胜)点属性

(1) 所有终结点是必败点（P点）； //容易理解

(2) 从任何必胜点（N点）操作，至少有一种方法可以进入必败点（P点）； //就是那种我们要走的方法

(3)无论如何操作， 从必败点（P点）都只能进入必胜点（N点）. //对手走完又只能把N留给我们

取子游戏算法实现

步骤1:将所有终结位置标记为必败点（P点）；

步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）

步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ；

步骤4: 如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2 /*

上面的说法似乎不太好理解。我简单讲下。显然我们可以从终结条件递推回来。往后往前开始扫描，（终结状态方向为后）

a.如果当前是P点，那么一步（向前）可以走到的都是N点

b.如果当前点未标明P/N属性，那么看看该点向后走是不是都只能到达N点，如果是，那么该点是P点。

c.如果该点是N点，倒无法确定什么。

如果没办法标一个点，那么异常结束。

*/

2. 阶梯博弈

http://blog.csdn.net/kk303/article/details/6692506

阶梯博弈（staircase）游戏开始时有许多硬币任意分布在楼梯上，共n阶楼梯从地面由下向上编号为0到n。游戏者在每次操作时可以将楼梯j(1<=j<=n)上的任意多但至少一个硬币移动到楼梯j-1上。游戏者轮流操作，将最后一枚硬币移至地上的人获胜。 首先是对阶梯博弈的阐述...博弈在一列阶梯上进行...每个阶梯上放着自然数个点..两个人进行阶梯博弈...每一步则是将一个集体上的若干个点( >=1 )移到前面去..最后没有点可以移动的人输..

斗法 由高僧斗法所想到

如这就是一个阶梯博弈的初始状态 2 1 3 2 4 ... 只能把后面的点往前面放...如何来分析这个问题呢...其实阶梯博弈经过转换可以变为Nim游戏。（www.61k.com]把所有奇数阶梯看成N堆石子..做nim..把石子从奇数堆移动到偶数堆可以理解为拿走石子..就相当于几个奇数堆的石子在做Nim..( 如所给样例..2^3^4=5 不为零所以先手必败)为什么可以这样来转化？ 假设我们是先手...所给的阶梯石子状态的奇数堆做Nim先手能必胜...我就按照能赢的步骤将奇数堆的石子移动到偶数堆...如果对手也是移动奇数堆..我们继续移动奇数堆..如果对手将偶数堆的石子移动到了奇数堆..那么我们紧接着将对手所移动的这么多石子从那个奇数堆移动到下面的偶数堆...两次操作后...相当于偶数堆的石子向下移动了几个..而奇数堆依然是原来的样子...即为必胜的状态...就算后手一直在移动偶数堆的石子到奇数堆..我们就一直跟着他将石子继续往下移..保持奇数堆不变...如此做下去..我可以跟着后手把偶数堆的石子移动到0..然后你就不能移动这些石子了...所以整个过程..将偶数堆移动到奇数堆不会影响奇数堆做Nim博弈的过程..整个过程可以抽象为奇数堆的Nim博弈...

其他的情况...先手必输的...类似推理...只要判断奇数堆做Nim博弈的情况即可... 为什么是只对奇数堆做Nim就可以...而不是偶数堆呢？...因为如果是对偶数堆做Nim...对手移动奇数堆的石子到偶数堆..我们跟着移动这些石子到下一个奇数堆...那么最后是对手把这些石子移动到了0..我们不能继续跟着移动...就只能去破坏原有的Nim而导致胜负关系的不确定...所以只要对奇数堆做Nim判断即可知道胜负情况...

3. 阶梯博弈变形

http://poj.org/problem?id=1704

斗法 由高僧斗法所想到

/* 如上如图所示：排成直线的格子上有n个格子，棋子i在左数第pi个格子上。[www.61k.com） G和B轮流选择一个棋子向左移动。每次移动可以移动一格及以上任意多个格， 但是不允许超其他的格子，也不允许将两个棋子放在同一个格子内。 无法移动就失败了。

转化： 如果将棋子两两看出一个整体考虑，我们就可以把这个游戏转为Nim游戏。先将棋子的个数的奇偶分情况讨论。

偶数：___1____5____8______10

就可以转化为

第一堆 5-1-1=3 个

第二堆 10-8-1=1 个。

为什么能这样转化？

考虑其中的一对棋子，将右边的棋子向左移动就相当于从Nim的石子堆中，取走石子 。 另一方面，将左边的棋子向左移动，石子的数量就增加了。这就与Nim不同。但是，即便对手增加了石子的数量，只要将所加部分减回去就回到了原来的状态；即便增加了石子的数量，只要对手将所加的部分减回去也就回到原来状态了。

偶数编号堆中的棋子个数不会影响局面的输赢状态。因为如果一个棋手将一些棋子从偶数编号堆移到奇数编号的堆中，那么他的对手总是可以将相同数目的棋子从这个奇数编号的堆中移动到编号更小的偶数编号堆中。移动偶数编号堆中的棋子并不会让对手无法移动。因此，一旦有棋子从奇数编号的堆中移动到偶数编号的堆中，那么这些棋子是不会影响局面的胜负状态的。

奇数：将最左边的0看出起始点就转化成偶数个了。

*/

斗法 由高僧斗法所想到

#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int f[1003];

int main()

{

int T,n,i,k;

while(scanf("%d",&T)>0) {

}

while(T--) { } return 0; scanf("%d",&n); for(i=1;i<=n;i++) if(n%2==1) f[++n]=0; k=0; sort(f+1,f+1+n); for(i=n;i>=1;i=i-2) } k=k^(f[i]-f[i-1]-1); printf("Bob will win\n"); if(k==0) else printf("Georgia will win\n"); scanf("%d",&f[i]);

4. 高僧斗法

斗法 由高僧斗法所想到

古时丧葬活动中经常请高僧做法事。［www.61k.com）仪式结束后，有时会有“高僧斗法”的趣味节目，以舒缓压抑的气氛。节目大略步骤为：先用粮食（一般是稻米）在地上“画”出若干级台阶（表示N级浮屠）。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人，其它任意。

if(c=='\n')

break;

}

count=i;

for(i = 0;i < count-1;i++)//最后小和尚的位置，代表总的台阶数：a[i-1]即a[count-1]

斗法 由高僧斗法所想到

b[i]=a[i+1]-a[i]-1;//数组b存储相邻两个小和尚之间没有人的台阶数，形成堆！！ b[count-1]=0;//最后的小和尚只能为0，因为游戏最后所有的小和尚都会集中在最后的台阶上

sum=b[0];//多解，有解的话输出一个最小解，故sum为b[0]（从下面开始第一个小和尚与第二个小和尚之间的台阶数）

/*

参与运算的两个值，如果两个相应位相同，则结果为0，否则为1。(www.61k.com］即：0^0=0， 1^0=1， 0^1=1， 1^1=0

*/

for(i=2;i<count;i=i+2)

1，

b[i-1]-=j;

}

}

return 0;

}

/*

1 3 5 7 12 14 17 26 38 45 66 100

66 84

*/

sum^=b[i];//sum的初值为b[0]，求奇数堆的异或之和！！ if(sum==0) //所有小和尚对应的没有人的台阶数都为0 printf("-1\n");//无解,所有小和尚相互之间没有台阶，而且都到了最后的台阶上。 else { for(i=0;i<count;i++)//共count/i个小和尚，暴力破解！ for(j=1;j<=b[i];j++) { b[i]-=j;//i位置上的台阶数减1(j)：即下面的小和尚上一个台阶 if(i!=0)//如不是第一小和尚，则将i的前面位置上的小和尚台阶数加1， b[i-1]+=j; sum = b[0]; for(k=2;k<count;k=k+2) sum^=b[k]; if(sum == 0){ printf("%d %d\n",a[i],a[i]+j);//输出A值较小的解 break; } b[i] +=j;//i位置上的台阶数加1，即上面的小和尚上一个台阶 if(i != 0)//如不是第一小和尚，则将i的前面位置上的小和尚台阶数减

本文标题：由方仲永所想到的-由方仲永所想到的
本文地址： http://www.61k.com/1069629.html