概述
一. 巴什博奕（Bash Game）：
A和B一块报数，每人每次报最少1个，最多报4个，看谁先报到30。比如第一次报数，A报k个数，那么B报5-k个数，那么B报数之后问题就变为，A和B一块报数，看谁先报到25了，进而变为20,15,10,5，当到5的时候，不管A怎么报数，最后一个数肯定是B报的，可以看出，作为后手的B在个游戏中是不会输的。
原理：如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。也就是把全部数以m+1个为一组分开。我们可以找到这么一个整数x和r，使n=x*（m+1）+r，当(m+1) | n时，也就是r=0时，后手会赢
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m)
if(n%(m+1)==0) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
return 0;
}
二. 尼姆博弈（Nimm Game）：
尼姆博弈指的是这样一个博弈游戏：有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。取完最后一个为胜！
我们假设有三堆物品用(a,b,c)来表示。我们用（a，b，c）表示某种局势，其中a,b,c分别表示当你选择时每一堆剩余的物品数。
.无论谁面对某种局势时，都必败的话，我们称这种局势为奇异局势。我们先来看奇异局势：
①首先（0，0，0）显然是奇异局势。
②第二种奇异局势是（0，n，n）。因为在这种情况下无论你拿走多少件物品，对方都可以拿走和你一样多的物品，这样你必败
③其次（1，2，3）也是奇异局势。因为无论你怎么拿，对手都可以将它变为（0，n，n）格式。
任何奇异局势(a,b,c)都有a xor b xor c =0。该结论可以推广至若干堆，都是成立的。
如果我们面对的是一个非奇异局势(a,b,c),要如何变为奇异局势呢？假设a < b< c,我们只要将c 变为a xor b,即可,因为有如下的运算结果: a xor b xor (a xor b)=(a xor a) xor (b xor b)=0 xor 0=0.要将c 变为a xor b,只要从c中减去c-(a xor b)即可.
也就是判断a xor b xor c 是否为0，如果为零，则先手必败，否则先手 必胜
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
int n,ans,temp;
while(cin>>n)
{
temp=0;
for(int i=0;i<n;i++)
{
cin>>ans;
temp^=ans;
}
if(temp==0) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
}
return 0;
}取完最后一个为败！
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int ans=0;
int flag=0;
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
ans^=x;
if(x>1)
flag++;
}
cout<<"ans:"<<ans<<' '<<flag<<endl;
if((ans&&!flag)||(!ans&&flag))//当奇数个1 或 有多个相同的偶数 时先手一定输
printf("Brothern");
else
printf("Johnn");
}
return 0;
}
给出n堆石子，每堆都有相应个数，最后问先手一开始有多少种取子方式能够取得最终的胜利。
其实把异或和算出来，然后用异或和去异或每个堆(因为偶数次异或，相当于抹去了这个值，比如 1^2==3,1^2^2=1，相当于抹去了2)，也就是看这个堆对最终的异或和有没有贡献，若有贡献，则这是一种走法
#include<iostream>
using namespace std;
int a[1005];
int main()
{
int n;
while(cin>>n&&n)
{
int ans=0;
int Count=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
ans^=a[i];
}
for(int i=0;i<n;i++)
{
if((ans^a[i])<a[i])//如果对ans是有贡献
Count++;//如果有 则方法数+1
}
cout<<Count<<endl;
}
}
Nim Staircase博奕:
这个问题是尼姆博弈的拓展：游戏开始时有许多硬币任意分布在楼梯上，共n阶楼梯从地面由下向上编号为0到n。游戏者在每次操作时可以将楼梯j(1<=j<=n)上的任意多但至少一个硬币移动到楼梯j-1上。游戏者轮流操作，将最后一枚硬币移至地上（0号）的人获胜。
其实阶梯博弈经过转换可以变为Nim..把所有奇数阶梯看成N堆石子..做nim..把石子从奇数堆移动到偶数堆可以理解为拿走石子..就相当于几个奇数堆的石子在做Nim 。假设我们是先手...所给的阶梯石子状态的奇数堆做Nim先手能必胜...我就按照能赢的步骤将奇数堆的石子移动到偶数堆...如果对手也是移动奇数堆..我们继续移动奇数堆..如果对手将偶数堆的石子移动到了奇数堆..那么我们紧接着将对手所移动的这么多石子从那个奇数堆移动到下面的偶数堆...两次操作后...相当于偶数堆的石子向下移动了几个..而奇数堆依然是原来的样子...即为必胜的状态...就算后手一直在移动偶数堆的石子到奇数堆..我们就一直跟着他将石子继续往下移..保持奇数堆不变...如此做下去..我可以跟着后手把偶数堆的石子移动到0..然后你就不能移动这些石子了...所以整个过程..将偶数堆移动到奇数堆不会影响奇数堆做Nim博弈的过程..整个过程可以抽象为奇数堆的Nim博弈...
结论：将奇数楼层的状态异或，和为0则先手必败，否则先手必胜。
#include<iostream>
#include<cmath>
using namespace std;
int num[100];
int main()
{
int n;
cin>>n;
int temp=0;
for(int i=0;i<n;i++)
{
cin>>num[i];
if(i&1)//奇数堆
temp^=num[i];
}
if(temp)
cout<<"先手必胜"<<endl;
else
cout<<"先手必败"<<endl;
}
三. 威佐夫博弈（Wythoff Game）：
有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜.
直接说结论了，若两堆物品的初始值为(x，y)，且x<y，则另z=y-x；记w=（int)[ ( (sqrt(5)+1) /2 )*z ]；若w=x，则先手必败，否则先手必胜。
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int x,y;
cin>>x>>y;
int z=abs(y-x);
if((int)(((sqrt(5)+1)/2)*z)==min(x,y))
cout<<"后手必胜"<<endl;
else
cout<<"先手必胜"<<endl;
}
四. 斐波那契博弈：
有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。
结论是：先手胜当且仅当n不是斐波那契数（n为物品总数）
#include<iostream>
#include<cmath>
using namespace std;
int f[100];
void Init()//斐波那契数列
{
f[0]=f[1]=1;
for(int i=2;i<=100;i++)
{
f[i]=f[i-1]+f[i-2];
}
}
int main()
{
int n;
cin>>n;
Init();
bool flag=false;
for(int i=0;f[i];i++)
{
if(f[i]==n)
{
flag=true;
break;
}
}
if(flag)
cout<<"后手必胜"<<endl;
else
cout<<"先手必胜"<<endl;
}
最后
以上就是烂漫小甜瓜为你收集整理的基本博弈论（四大博弈+拓展nim）的全部内容，希望文章能够帮你解决基本博弈论（四大博弈+拓展nim）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复