一、巴什博奕（点击进入例题）

1.只有一堆n个物品

2.两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。

3.最后取光者得胜。

分析：

•当 n = m + 1 时，第一个人不可能获胜；

•当 n = k*(m + 1) + r 时，先取者拿走 r 个，那么后者再拿（1~m）个 ， 此时 n =（k-1）*（m+1）+s

  先取者再拿走s 个 最后总能造成 剩下n=m+1 的局面

•若n=k*(m+1) 那么先取者必输

求解巴什博弈模板：

int Bash_Game(int n,int m)//是否先手有必赢策略
{
    if (n%(m+1)!=0)
	return 1;
    return 0;
}

二、威佐夫博弈（点击进入例题）

1.有两堆各若干个物品

2.两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限

3.最后取光者得胜

分析：

•两堆石子的状态为 [ak,bk] （满足ak<=bk）

•当 ak=(k*(√5+1)/2), bk=ak+k 时满足奇异局势，那么则先手输，反之则先手赢

求解威佐夫博奕模板： 

int Wythoff_Game(int a,int b)
{
    double x=(1+sqrt(5))/2;
    int n=b-a;
    if(a==(int)(x*n))
        return 1;
    return 0;
}

三、尼姆博弈（点击进入例题）

1.有三堆各若干个物品

2.两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限

3.最后取光者得胜。

分析：

用0与每个数异或,如最后结果为0,则后手胜

设一数组a[m],令sum=0

循环与数组每一个数据异或（sum^=a[i]）

sum最后等于0则后手胜

求解尼姆博弈模板：

//a[m]每堆物品的数量  sum=0
int Nimm_Game(int m)
{
	for(int i=0;i<m;i++)
		sum = sum ^ a[i];
	if(sum == 0)
		return 0;
	return 1;
}

四、斐波那契博弈（点击进入例题）

1.有一堆个数为n的石子，游戏双方轮流取石子

2.先手不能在第一次把所有的石子取完；

3.之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）

求解斐波那契博弈模板：

int Fib_Game(int n)
{
	f[1]=1;f[2]=1;
	for(int i=3;i<=50;i++)
    {
        f[i] = f[i-1] + f[i-2];
        if(f[i]==n)return 1;
        if(f[i]>n)break;
    }
	return 0;
}

五、环形博弈

1.n个石子围成一个环

2.每次取一个或者取相邻的2个

求解环形博弈模板：

石子数<=2先手赢,否则后手赢

int fun(int n)
{
    if(n<=2)return 1;
    return 0;
}

最后

以上就是乐观战斗机为你收集整理的博弈论简单入门 【巴什博奕、威佐夫博弈、尼姆博弈、斐波那契博弈、环形博弈 】模板一、巴什博奕（点击进入例题）二、威佐夫博弈（点击进入例题）三、尼姆博弈（点击进入例题）四、斐波那契博弈（点击进入例题）五、环形博弈的全部内容，希望文章能够帮你解决博弈论简单入门 【巴什博奕、威佐夫博弈、尼姆博弈、斐波那契博弈、环形博弈 】模板一、巴什博奕（点击进入例题）二、威佐夫博弈（点击进入例题）三、尼姆博弈（点击进入例题）四、斐波那契博弈（点击进入例题）五、环形博弈所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。