首页 > 代码库 > 【博弈论】威佐夫博弈

【博弈论】威佐夫博弈

威佐夫博弈

    威佐夫博弈:有两堆石子,每次一个人可以两堆同时取相同数量的石子,也可以只取其中一堆的石子,最后谁取完谁获胜,请问先手还是后手胜?

      对于学过一些博弈论基础的来说,我们需要找到那些能让先手必输的局势,那么由这些局势在规定范围内拓展的局势也是先手必输的局势(但在这里双方自由选取,不适用)。我们可以得出一些局势使A必输:(0,0) (1,2) (3,5) (4,7) (6,10(8,13(9,15(11,18)

(12,20)……我们称这些局势为奇异局势

      不难发现,如果我们标记(0,0)为第0项的话,那么ak是前面还没有出现过的最小数字,bk=ak+k

      对于奇异局势来说,有以下性质:

  1. 任何自然数都一定包含在一个奇异局势中。
  2. 任意操作都可以将奇异局势转变为非奇异局势。
  3. 可以将非奇异局势转变为奇异局势。

     那么,当我们面对下列情况时,可以这样应对:

     当a=b时,两堆同时取a

     当a=ak,b>bk时,2堆取b-bk个

     当a=ak,b<bk时,2堆取a-a(b-a)个

     当a>ak,b=bk(ak+k)时,1堆取a-ak个

     当a<ak,b=bk(ak+k)时,从2堆中拿走若干变成奇异局势

 

    如何判断一个数对是不是奇异局势呢?

    当a=(下取整)k*(1+√5)/2,b=ak+k时(k为任意非负整数)局势为奇异局势

 

 

                                                取金币

题目描述

小A小B共同赚取了两堆金币,数量分别为 N 和 M 。现在他俩轮流从中取金币,只能从以下两种取法中选择一种选取:

  1. 选择任意一堆,取走任意数量的金币;
  2. 从两堆中同时取走数量相同的金币。

最后把金币取完的人为胜利者。小A小B都想取得胜利,都会采取最优策略。现在请你帮小A计算一下,如果他先取,能否取得胜利。

输入格式

* 输入一行,输入两个正整数 N 和 M,表示两堆金币的数量。

输出格式

* 输出一行,输出一个数字。如果小A可以取得胜利,请输出 1,反之输出 0

样例输入1

4 5

样例输出1

1

样例输入2

3 8

样例输出2

1

代码:

#include<iostream>#include<cstring>#include<cstdio>#include<queue>#include<stack>#include<vector>#include<algorithm>#include<cmath>using namespace std;const int INF = 9999999;#define LL long longinline int read(){	int x=0,f=1;char c=getchar();	for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;	for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;	return x*f;}int N,M; int main(){	//freopen(".in","r",stdin);	//freopen(".out","w",stdout);	N=read(),M=read();	double t=(1.0+sqrt(5))/2.0;	if(N>M) swap(N,M);	int tmp=M-N;	if(N==(int)(t*tmp)) printf("0");	else printf("1");	return 0;}

 

【博弈论】威佐夫博弈