大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
博弈论基础
博弈论又被称为对策论(Game Theory),既是现代数学的一个新分支,也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用,是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。
引入:囚徒困境
囚徒困境的故事讲的是,两个嫌疑犯小A、小B作案后被警察抓住,分别关在不同的屋子里接受审讯。警察知道两人有罪,但缺乏足够的证据。警察告诉每个人:如果两人都抵赖,各判刑一年;如果两人都坦白,各判五年;如果两人中一个坦白而另一个抵赖,坦白的放出去,抵赖的判十年。
于是,每个囚徒都面临两种选择:坦白或抵赖。
在不和小B商量的情况下,作为小A的你是选择招供坐牢5年或0年,还是会选择抵赖坐牢10年或1年呢?
一般的人都会选着保险一点的招供吧。
反观小B,也一定会做出同样的选择,也就是招供。换句话说,只要两名囚徒都是自私且理性的,那么双方都会同时选择招供,结果就是双方各判5年。
在这个场景中,双方都无法单方面改变自己的博弈策略(单方面改变只会让自己蒙受损失),使得局面进入了一个微妙而又稳定的平衡,这个平衡被称为纳什均衡。
在现实中,也有很多类似的现象,比如家长给孩子报越来越多的课外班,比如高三考生备战高考,卷起来了啊.从局外人看来,许多竞争都是显而易见双输的局面,但是我们没有办法,因为我们都是参与博弈的“囚徒”。
ICG博弈
所讨论的博弈问题满足以下条件:
玩家只有两个人,轮流做出决策。
游戏的状态集有限,保证游戏在有限步后结束,这样必然会产生不能操作者,其输。
对任何一种局面,胜负只决定于局面本身,而与轮到哪位选手无关。
取石子游戏:取石子游戏是一个古老的博弈游戏,发源于中国,它是组合数学领域的一个经典问题。它有许多不同的玩法,基本上是两个玩家,玩的形式是轮流抓石子,胜利的标准是抓走最后的石子。玩家设定: 先取石子的是玩家A(先手A),后取石子的是玩家B(后手B)。
经典的三种玩法
一、巴什博奕(Bash Game)
二、尼姆博奕(Nimm Game)
三、威佐夫博奕(Wythoff Game)
(一)巴什博弈
1堆n个石子每次最多取m个、至少取1个
Case 1:如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。
Case 2:n=(m+1)*r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后者拿走k(1≤k≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者肯定获胜。
Case 3:n=r*(m+1),先手拿走k(1≤k≤m)个,那么后手再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,则后手胜,先手必败。
总之,要保持给对手留下(m+1)的倍数,就能最后获胜。
术语:正经人称(m+1)的局面为奇异局势
变相的玩法
两个人轮流报数,每次至少报一个,最多报十个,谁能报到100者胜。(等价于从一堆100个石子中取石子,最后取完的胜)
题面:
题面意思:有一堆k个的石头,每人轮流拿1,2,..L个石头,数据范围是3 <= K <= 100 000 000 ,2 <= L < K。输入k的值,要求输出最小的L,使得后者胜。
在理解了巴什博弈之后来看这题还是思路比较清晰的,首先想让后手胜,就必须把(1+L)的局面留给先手。这题没问我们谁会赢,问的是后手要赢的最小L值为多少。那我们就找到能被k整除的最小大于2的因数,之后减1输出就是答案了。
于是有了以下代码注意下(poj用不了万能头文件,编译器要求有点严格。):
//#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100005;
ll n;//石子数量
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
ll i;
for(i=2;i<n;i++)//依次找最小的因子
{
if(n%(i+1)==0)
{
cout<<i<<endl;
break;
}
}
if(i==n) cout<<0<<endl;//找不到的情况下输出0
return 0;
}
就是说数据范围1e8,就超时快乐,TEL了哈哈哈哈哈哈。由于循环2~n,时间复杂度是O(n)。
再有一个新的思路就是,遍历一遍所有的n的因数,存起来,在输出最小大于等于3的因数减一。一下代码时间复杂度为O(log n)。AC快乐。
//#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll n,a[N];//n为石头总数,a[i]存n的因数
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
int temp=0;
for(int i=1;i*i<=n;i++)
{
if(n%i==0&&i*i!=n) a[temp++]=i,a[temp++]=n/i;
//注意要区别开类似n=4时,因数为1,2,4.而不是1,2,2,4的情况
else if(n%i==0&&i*i==n) a[temp++]=i;
}
sort(a,a+temp);//从小到大排序一下
for(int i=0;i<temp;i++)
{
if(a[i]>=3)//找到最小大于等于3的因数,减一输出
{
cout<<a[i]-1<<endl;
break;
}
}
return 0;
}
(二)尼姆博弈
有n堆石子,每堆石子的数量是a1,a2,a3……,二个人依次从这些石子堆中的一个拿取任意的石子,至少一个,最后一个拿光石子的人胜利
n=1: 先手全拿,先手必胜。
n=2:有两种情况,一种可能相同,一种情况一堆比另一堆少(多)
(m,m) 按照“有一学一,照猫画猫”法,先手必输。
(m,M)先手先从多的一堆中拿出(M-m)个,此时后手面对(m,m)的局面先手必胜。
术语:正经人称(m,m)的局面为奇异局势
n=3:(m,m,M)先手必胜局,先手可以先拿M,之后变成了(m,m,0)的局面,是不是很熟悉~
(a1,a2,a3)的话,举个例子(1,2,3),先手取完之后可能的局面为(0,2,3),(1,1,3),(1,0,3),(1,2,2),(1,2,1),(1,2,0)都是之前讲过的,情况如下:
前人告诉我们的规律是:异或的结果均为0
获胜情况的讨论
面对异或结果为0的玩家必输。
结果不为0,则玩家有获胜的取法。
题面:
看懂了尼姆博奕,这个题目就是分分钟AC咯。
上代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll n,a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int ans=a[0];
for(int i=1;i<n;i++) ans^=a[i];//^就是做异或运算
if(ans==0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
return 0;
}
(三)威佐夫博弈
有两堆各若干个物品,两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
举一个例子:局势是(1,2),先手有四种取法,动动你聪明的脑子就会发现无论先手怎么取,后手都能胜利,也就是说(1,2)是奇异局势。
没脑子的人来看看分析咯:
先手从第一堆里面拿1个,后者拿光后面的2个,后者胜。
先手从第一堆和第二堆里面同时拿1个,后者只能拿走第二堆剩下的1个,后者胜。
先手从第二堆里面拿2个,后手拿走第一堆的1个,后者胜.
先手从第二堆里面拿1个,后手从第一堆和第二堆里面同时拿走1个,后者胜。
假设现在的局势是(3,5):
(1)先手在“3”中取1个,后手就可以在“5”中取走4个,这样就变成了(1,2)的局势
(2)先手在“3”中取2个,后手就可以在 “5” 中取走3个,这样也变成了(1,2)的局势
(3)先手在“5”中取1个,后手就在 “3”和“5” 中各取走2个,这样成了(1,2)的局势
(4)先手在”5”中取2个,后手就在 “3”和”5”中各取走3个,这样变成了(0,0)的局势,先手输
(5)先手在“5”中取3个,后手就在 “3”和“5” 中各取走1个,也变成了(1,2)的局势
(6)先手在“5”中取4个,后手在“3”中取走1个,还是(1,2)的局势
我们可以来找找那些先手必输局势的规律(奇异局势)
- 第一种(0,0)
- 第二种(1,2)
- 第三种(3,5)
- 第四种 (4 ,7)
- 第五种(6,10)
- 第六种 (8,13)
- 第七种 (9 ,15)
- 第八种 (11 ,18)
- 第n种(a,b)
我们会发现他们的差值是递增的,分别是0,1,2,3,4,5,6,7……n
还有一个规律(正常人都发现不了):a=(b-a)*1.618向下取整
就是:a = int(b – a)*1.618
注:这里的int是强制类型转换,注意这不是简单的四舍五入,假如后面的值是3.9,转换以后得到的不是4而是3,也就是说强制int类型转换得到的是不大于这个数值的最大整数。
有些题目要求精度较高,我们可以用下述式子来表示这个值:
1.618 = (sqrt(5.0) + 1) / 2
头文件:include<math.h>
题面:
代码:
//#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll a,b;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(cin>>a>>b)//多组输入!!!
{
double flag= (sqrt(5.0) + 1) / 2.0;//精度高一些用double来存1.618
if(a>b) swap(a,b);//保证b要比a大,后面有用到b-a
if(a==int((b-a)*flag))cout<<0<<endl;//先手面对奇异局势必输
else cout<<1<<endl;
}
return 0;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/181728.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...