雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

《编程之美》读书笔记061.13 NIM(3)两堆石头的游戏

 

问题:

假设有两堆石子,两人轮流取石子,每次可以从一堆取任意个石子,或者从两堆取相等数量的任意个石子,但不能不取。

若先把石子取光的一方为胜方,先取者有什么必胜策略?

若先把石子取光的一方为输方,先取者的策略要进行怎样调整?

 

记得初中时在学校门口的书店,买到一本《智力游戏中的数学方法》,当时如获至宝。书中提到一个“皇后登山”游戏,就是在空的围棋棋盘上放一个棋子,该棋子每次只能向上或向右或沿对角线向右上方向移动(和国际象棋中的皇后移动相似),可以移动任意格,但不能不移动,两人轮流移动棋子,先将棋子移动到右上角者赢,问先移棋者的必胜策略。书中还提到这个捡石子游戏,并说明这两个游戏是“同构”,必胜策略是相同的。

 

NIM游戏的“必胜策略”可以概括为:找出最终获胜局面具有的某种性质,对具有该性质的局面的一次操作得到的新局面必然不具有这种性质,而对不具有该性质的局面,总可以通过一次操作,得到一个具有该性质的新局面。假设游戏双方分别为AB,只要A方能到达具有该性质的某个局面,则B方一定不能到达具有该性质的任意一个局面,从而不能到达获胜局面,因而B方必败,即A方必胜。这种性质可以是对称性(1.11的策略)、每堆数二进制表示各个位的和的奇偶性(1.12的策略)、属于某个集合(1.13的策略)。

 

对于1.13NIM游戏,就是寻找这样的一系列关键局面(包括最终获胜局面),总可以通过一次操作将一个非关键局面转为关键局面,而一次操作必将一个关键局面转为非关键局面。因此,从一个关键局面到另一个关键局面至少要(并且能只要)两次操作(“两次操作原则”)

 

<a, b> (a<=b)表示两堆的石子数分别为ab的局面。对所有的关键局面<x, y>,按x值大小升序排列,最终可用<Fn, Gn >(其中 Fn <= Gnn>=0)来表示第n个关键局面Mn, 并记<F0, G0 >为最终获胜局面M0(对拿到最后一个获胜的,M0=<0,0>,而对拿到最后一个输的,M0=<0,1>),定义Tn=Gn-Fn >=0。每次取石子的操作规则为:从某一堆取任意个石子,或从两堆同时取任意个相同的石子。从M0开始利用这个规则去除不合的局面。根据规则,显然在已知M0 M1 … Mn 情况下,Mn+1 应该满足:Fn+1不与任意一个FiGi0<=i<=n)相同,Tn+1也不与任意一个Ti0<=i<=n)相等。因而,可以假设:Fn+1是不与任意一个FiGi0<=i<=n)相同的最小非负整数,Tn+1是不与任意一个Ti相等的最小非负整数(0<=i<=n。由该假设得到的<Fn, Gn >即为关键局面,符合“必胜策略”。

 

(证:由假设,显然有Fi >= Ti (i>=1)

 对关键局面<Fn, Gn >,设石子较少的那堆为X,较多的那堆为Y

  A方若在X堆,或在两堆同时取k个石子,则由假设可知,X堆剩余的石子数必然与某个i或某个Gi0<=i<n)相等,B方可在Y堆取石子,到达另一个关键局面< Fi, Gi >)。

⑵ A方若在Y堆取走k个石子:

  k <= Tn,由假设必然可找到i,使得Ti=Tn-k0<=i<n),B方只要在两堆同时取Fn-Fi个石子,即可到达关键局面< Fi, Gi >)。

⒉ 若k > Tn,则B堆剩余石子小于Fn,必然与某个i或某个Gi0<=i<n)相等。

A 若与某个Gi相等,则A堆只要再取Fn-Fi个石子,即可到达关键局面< Fi, Gi >

B  若与某个Fi相等:

如果Fn>Gi则在则A堆只要再取Fn-Gi个石子,即可到达关键局面< Fi, Gi >

如果Fn<Gi,必然可以找到j0<=j<i)使得Tj=Fn-Fi,两堆同时取Fi-Fj个石子到达关键局面< Fj, Gj >

 对非关键局面<a, b>,由假设可知,a必与某个i或某个Gi0<=i<n)相等,因而,可以从另一堆取石子数,到达关键局面< Fi, Gi >;或从关键局面< Fi, Gi >某堆取石子到达非关键局面<a, b>,而由上面的证明可知,可以再通过一次操作,到达某个关键局面< Fj, Gj >。因此,总可以一次操作从非关键局面到达关键局面。

总之,由假设得到的关键局面符合“必胜策略”。)

 

拿最后一个赢:

n

0

1

2

3

4

T

0

1

2

3

4

F

0

1

3

4

6

G

0

2

5

7

10

由于T0=0,根据Tn的定义可得Tn=n,刚好是beatty序列,可由beatty序列的通项公式求得Fn的通项公式

 

拿最后一个输:

n

0

1

2

3

4

T

1

0

2

3

4

F

0

2

3

4

6

G

1

2

5

7

10

n>=2时,关键局面与拿最后一赢的相同。

 

胜利条件为拿最后一个赢时,要找出所有关键局面(即书中的不安全点),最快的办法就是得用通项公式,虽然通项公式有无理数,转成浮点数,引起的误差对结果没多大影响(只有当N极大时,才会使结果不对)。对浮点计算十分昂贵的平台,还是用筛选法,利用“在两个GiGj间的数必然是某个Fk值”,筛选过程只须保留一部分Gn就可以计算出新的Fn

另外,对关键点<Fn, Gn=Fn+n>,当n>1时,从1FnFn个数,有nFi,还有Fn-n个在Gj。因而0<Fn-n<n,即有:n< Fn<2*n (n>1),在判断<x,y>y>=x)是否是关键点,先判断是否满足这个不等式,如果满足,才生成第y-xF值再进行判断。由通项公式可知,

Fnint(1.618*n),可以强化边界条件为:int(n*3/2)int(n*7/4)

 

(书上给出的定理是beatty定理。该定理的证明相当简单,有兴趣的可以google下。另外,上个世纪五六十年代,我国数学家曾在《数学通论》(有网络版)发表过证明,好像还用到了Fibonacci的通项公式。)


void nim(int num) //print all the unsafe points
{
  assert(num
>0);
  vector
<int> g(num+3);
  
int n=2;            // f[2] is between [ g[1]+1 , g[2]-1 ]
  g[1]=2; g[2]=99;   //  g[2] should be initialized with a value above g[1]+1=3.
  int fn=g[1];
  
int *low=&g[2];
  
int *high=&g[n];
  
for( ; n <= num; ++n){
    
if++fn == *low){
      
++low;
      
++fn;
    }

    
*high++ = fn + n;      //f(n)=fn, g(n)=f(n)+n
  }


  
for(int i=1;i<=num;++i) {
    
//const double SS=(1.0+sqrt(5))/2.0+1.0;
    
//if ( (int)(i*SS) != g[i] )   cout<<"Error: " << i<< "\n";
    cout<< g[i]-i<< ","<<g[i]<<"  ";
  }

  cout
<<endl;

}




bool nim(int x, int y)     //whether win the game
{
  assert(x
>=0);
  assert(y
>=0);
  assert( 
!(x==0 && y==0));
  
int ff=x, gg=y, num;
  
if (x > y) ff=y, gg=x;   
  num
=gg-ff;            
  
if ( ff < num || ff > ( num << 1) ) return true;  //win the game

  vector
<int> g(num+3);
  g[
1]=2; g[2]=99;
  
int n=2, fn=g[1];
  
int *low=&g[2];
  
int *high=&g[n];
  
  
for( ; n <= num; ++n){
    
if ( ++fn == *low) ++low; ++fn;}
    
*high++ = fn + n;
  }
  

 
if (*--high == gg) return false;
 
else return true;
}



posted on 2010-08-15 23:58 flyinghearts 阅读(1862) 评论(0)  编辑 收藏 引用 所属分类: 编程之美

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理