首页 > 代码库 > 【博弈论】威佐夫博弈
【博弈论】威佐夫博弈
威佐夫博弈
威佐夫博弈：有两堆石子，每次一个人可以两堆同时取相同数量的石子，也可以只取其中一堆的石子，最后谁取完谁获胜，请问先手还是后手胜？
对于学过一些博弈论基础的来说，我们需要找到那些能让先手必输的局势，那么由这些局势在规定范围内拓展的局势也是先手必输的局势(但在这里双方自由选取，不适用)。我们可以得出一些局势使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
对于奇异局势来说，有以下性质：
- 任何自然数都一定包含在一个奇异局势中。
- 任意操作都可以将奇异局势转变为非奇异局势。
- 可以将非奇异局势转变为奇异局势。
那么，当我们面对下列情况时，可以这样应对：
当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 。现在他俩轮流从中取金币，只能从以下两种取法中选择一种选取：
- 选择任意一堆，取走任意数量的金币；
- 从两堆中同时取走数量相同的金币。
最后把金币取完的人为胜利者。小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;}
【博弈论】威佐夫博弈