博弈论讲解（一）
常见的博弈论有巴什博弈，威佐夫博弈，尼姆博弈，斐波那契博弈等等，今天暂时讲几个
巴什博奕：只有一堆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%(m+1）==0，则先手必输
变形：
如果条件不变，改成最后取光的人失败
结论：若（n-1）%（m+1）== 0 ，则后手胜利
if(n%(m+1)==0) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
二.威佐夫博奕
有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
A无论怎么取，B总是可以 针对着来
奇异局势下先手必败，非奇异局势下先手必胜。
（a，b）表示两堆物品的数量，也称之为局势
奇异局势：就是当A面对这个局势时就已经输了。你也可以理解成必输局面。比如（0,0）或者（1,2）（3,5）等等
那怎么知道一个局势是否为奇异局势
a与b满足这个条件：
ak =[k（1+√5）/2]，bk= ak + k
（k=0，1，2，…,n 方括号表示取整函数）ak<bk
整合一下
ak = [ ( bk - ak ) （ 1 + √5 ） / 2 ]
证明：略（其实我也不是很明白）
代码：
if(a>b) swap(a,b);
ans=floor((b-a)*(1+sqrt(5.0))/2.0);
if(ans==a) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
三.环形博弈
n个石子围成一圈，每次只能取相邻的k（1<=k<=n）个石子，取完者胜。
今天一个同学问我，我才想起来这个。。。
如果n<=k,先手必赢（也就是如果先手能一次拿完就输）
当k等于1时，n为奇先手胜，n为偶后手胜。
因为是环形，假如说A第一次没去完，那B只要取与A相对的石头，也就是A拿完后，还剩奇数个石头，B就拿与A对应位置的一个石头，如果剩偶数个，就拿对应位置的两个
这样就把一个环拆分成两个链，且每个链都是相等的
用sg定理，sg[x] ^ sg[x]= 0
这就是必败态，所以先手A输了
当k=1时，这就不用我讲了吧。。。
bool circle_game(int n,int k){
if(k>=n||k==1&&(n&1)) return 1;
return 0;
}
例题 HDU - 3951
Jozky86
原创文章 87获赞 4访问量 1295
关注
私信
展开阅读全文
作者：Jozky86
