博弈论（巴什博奕，威佐夫博弈，尼姆博弈）_博弈论公式

巴什博奕（Bash Game）：

只有一堆n个物品，两个人轮流从中取物，规定每次最少取一个，最多取m个，最后取光者为胜

举一个最简单的例子就是，当n=m+1时，此时不管先手取多少，后手都能把剩下的取完，拓展到n等于m+1的倍数时，不管先手取多少，后手都可以取（m+1减去先手取的个数）个，最后先手一定会面临n=m+1的情况，此时先手必败，否则先手必胜

程序代码：

#include<stdio.h>
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
    	if(n%(m+1)==0)  
			printf("先手必败\n");
   		else 
			printf("先手必胜\n");
	}
    return 0;
}

威佐夫博弈（Wythoff Game）：

有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利

这有一个公式：t=(int)((a-b)*(1.0+sqrt(5.0))/2.0);让t与较小堆石子数相比，如果相等先手必败，否则先手必胜

程序代码：

#include<stdio.h>
#include<math.h>
int main()
{
    int a,b,t;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
	    if(a<b)  
	    {
	    	a^=b;
	    	b^=a;
	    	a^=b;
		}
	    t=(int)((a-b)*(1.0+sqrt(5.0))/2.0);
	    if(t==b) 
			printf("先手必败\n");
	    else 
			printf("先手必胜\n");	
	}
    return 0;
}

尼姆博弈（Nimm Game）：

有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜

把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜

程序代码：

#include<stdio.h>
int main()
{
    int n,m,i,count;
    while(scanf("%d",&n)!=EOF)
    {
        count=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&m);
            count^=m;
        }
        if(count==0)  
			printf("先手必败\n");
        else 
			printf("先手必胜\n");
    }
    return 0;
}