巴什博奕,威佐夫博弈,尼姆博弈

  1. 巴什博奕(Bash Game):
  2. 威佐夫博弈(Wythoff Game):
  3. 尼姆博弈(Nimm Game):

巴什博奕(Bash Game):

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

我觉得最显著的特点就是两人拿的数目加起来是个定值,那么如果这个定值如果能被总数整除,则后手必胜。

1
2
3
4
5
6
7
8
9
10
#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;
}

威佐夫博弈(Wythoff Game):

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

结论了,若两堆物品的初始值为(x,y),且x<y,则另z=y-x;
记w=(int)[((sqrt(5)+1)/2)*z ];

若w=x,则先手必败,否则先手必胜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cmath>  
#include <iostream>
using namespace std;
int main()
{
int n1,n2,temp;
while(cin>>n1>>n2)
{
if(n1>n2) swap(n1,n2);
temp=floor((n2-n1)*(1+sqrt(5.0))/2.0);
if(temp==n1) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
}
return 0;
}

尼姆博弈(Nimm Game):

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

结论就是:把每堆物品数全部异或起来,如果得到的值为0,那么先手必败,否则先手必胜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}

转自CSDN

script>