ACM算法之博弈论

巴什博弈 

 一堆n个物品，两个人轮流从中取出1~m个，最后取光者胜。

如果n是m+1的倍数，则先手必输。如果不是则先手必胜。

对于先手来说如果不能一步到达必输态则先手必输，反之必胜。0是第0个必输态，m+1是第一个必输态，2*（m+1）是第二个必输态，n*（m+1）是第n个必输态。

if(n%(m+1)==0){return false;
elsereturn true;

威佐夫博弈

两堆物品,两人轮流从一堆或者两堆中取相同1~不限个，最后取光者胜。

如果(x,y)满足（[],[]）（nN*），则先手必输。如果不是则先手必胜。

对于先手来说如果不能一步到达必输态则先手必输，反之必胜。设（x，y）和（y，x）为第m个必输态，如果x或y在其他必输态的x，y中出现过，则可以一步到达必输态。如果x=y，则可以一步到达必输态，并且要使得必败态的x-y尽可能小，所以（a，a+n）为必败态，

引入Betty定理，a=[na],a+n=[n(a+1)]，可得，得a=(a=舍)，所以

  （[],[]）（nN*）为第n个必败态。

if(abs(x-y)*((sqrt(5)+1)/2)==min(x,y))return false;
elsereturn true;

尼姆博弈

三堆物品，两人轮流取，每次取其中一堆1~不限个，最后取光者胜。

（a，b，c）满足a^b^c=0则先手必输，反之必胜。

if(a^b^c==0)return false;
elsereturn true;

斐波那契博弈

一堆物n个，两人轮流取，不能取完，不能取超过上次两倍，最后取光者胜。

n满足斐波那契数列必输，反之必胜。

int a=0,b=1,c=1;
for(int i=2;1;i++){int d=c;d=a+b;a=b;b=c;c=d;if(c==n){return false;else if(c>n)return true;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！