文章目录
一.巴什博弈二.威佐夫博弈三.尼姆博弈一.巴什博弈
一堆n个物品,两个人从中轮流取出1~m个,最后取关者胜.
同余定理:n=K*(m+1)+r;先取者拿走r个,那么后者无论拿走(1~m)个先者只要拿的数目和为m+1那么先者必赢.反之若n=K*(m+1)+r,那么先者必输.
bool check(){if(n%(m+1)) return true;else return false;}
二.威佐夫博弈
有两堆若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利.
结论:先求出差值,差值*黄金分割比==最小值的话后手赢,否则先手赢
bool check(){double r=(sqrt(5.0)+1)/2;int d=abs(a-b)*r;if(d!=min(a,b)) return true;else return false}
三.尼姆博弈
n堆物品,两人轮流取,每次取某堆中不少于一个,最后取完者胜.
结论:将n堆物品数量全部异或后结果为0则必败
bool check(){int res=0;for(int i=1;i<=n;i++)res=res^arr[i];if(res) return true;else return false;}