博弈论基础入门

bash game

情况介绍

两个顶尖聪明的人在玩游戏,有n个石子,每人可以随便拿1−m个石子,不能拿的人为败者,问谁会胜利

分析

可以想到如果最终剩下m+1个石子,那么肯定先手必败。那么我们想到推出其他的m+1的倍数也就是说如果
n%(m+1)!=0也就是说n=k(m+1)+r (k,r为常数)那么我们先手可以完全先拿走r个石子然后后手不管你怎么拿我先手只要凑够m+1就行了最终肯定是先手能够获胜反之如果n=k(m+1)那么后手必胜所以我们可以得到最终代码

1
2
3
4
if(n%(m+1))
cout<<"first\n";
else
cout<<"second\n";

威佐夫博弈

情况介绍

有两堆各若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利。

分析

具体的推理我就不说了,网上各种推理。也就是说我们要判断当前状态(a,b)是否可以先手胜利的条件是求a,b的最大值然后求出差值来b-a然后看看(b-a)* r是不是等于a其中r是(1+sqrt(5))/2

1
2
3
4
5
6
7
8
9
10
11
int n,m;
cin>>n>>m;
int t1=min(n,m);
int t2=max(n,m);
int t3=t2-t1;
double r=(1+sqrt(5))/2;
int t4=r*t3;
if(t4==t1)
cout<<"Yes";
else
cout<<"no";

Nim game

情况介绍

有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

分析

这个就是一个比较常见的会出现变形的
首先接受NP
N为必胜点P为必败点
也就是说当前如果是N点那么经过两者的正确的操作那么先手必胜P点也是这样
其中包含三个性质
①N至少存在一种进入P
②P只能进入N
③所有的终结一定是P
也就是说如果当前是P那么下一点必须是N
如果要判断当前情况是不是N那么我们可以把当前的所有的数异或一下然后看看是不是等于0如果等于0那么就是一个P否则是一个N
这也就是nim和

1
2
3
4
5
6
7
8
9
10
int sum=0;
for(int i=0;i<n;i++)
{
cin>>num[i];
sum^=num[i];
}
if(sum)
cout<<"Yes";
else
cout<<"no";

SG函数

一看到这个我就想到csgo的SG553我自称他为帅哥函数或者傻狗函数。。。

分析

SG函数可以直接求出当前节点的NP属性如果SG[n]大于0那么代表当前的n是一个N否则是P

求解

SG函数靠递推求解,保证每次S集合都要清空即可

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;i++)
{
memset(s,0,sizeof(s));
for(int j=1;i-f[j]>=0&&j<=N;j++) //求解当前延伸
s[sg[i-f[j]]]=1;
for(int j=0;;j++) //求解最小的没有出现的整数
if(!s[j])
{
sg[i]=j
break;
}
}

应用

sg函数的f数组是分解的方式,也就是说如何分解。SG函数也是靠着分解然后一步一步递推的
然后就是如果有多个状态求他们的nim和即可也就是如果有三堆a,b,c那么求个sg[a]^sg[b]^sg[c]即可

就算是一分钱,也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于baccano 博客( http://baccano.fun ),版权所有,侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆?---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%