网站营销公司简介,游戏ui设计师网站有哪些,专门做家教的网站,广州五屏网站建设目录 前言#xff1a;
巴什博奕
威佐夫博奕#xff08;Wythoff Game#xff09;
尼姆博奕#xff08;Nimm Game#xff09; 前言#xff1a;
初次系统学习博弈题#xff0c;这篇文章我将从常见的博弈入手#xff0c;浅谈一下自己的感触。 巴什博奕 描述#xff1a…目录 前言
巴什博奕
威佐夫博奕Wythoff Game
尼姆博奕Nimm Game 前言
初次系统学习博弈题这篇文章我将从常见的博弈入手浅谈一下自己的感触。 巴什博奕 描述只有一堆n个物品两个人轮流从这堆物品中取物规定每次至少取一个最多取m个最后取光者得胜。 我们假设n(m1)*kr可以得出结论当r0的时候后者胜反之前者胜。下面给出证明
当r0时
n(m1)*k这个时候我们假设第一个人取x个物品x的范围是[1,m]因为两个人是绝顶聪明的所以第二个人可以取(m1-x)个物品这样在两个人进行一轮取物品的操作之后还剩下n(m1)*(k-1)个物品以此类推最后一定是第二个人赢。
当r≠0时
nm1)*kr这个时候第一个人取r个物品这样后面的问题就变成了r0时候的情况此时一定是第一个人赢。 总结起来就是若n%(m1)0第二个人胜反之第一个人胜。 int n,m;int kn%(m1);if(k0)coutB Winendl;else coutA Winendl; 巴什博奕延伸如果说最后一个取物品的人输了该怎么办
这时候假设 n-1(m1)*kr
当r0时
第一个人取x个第二个人取(m1-x)个那么按照这种方法最后多出来的那一个物品会被第一个人取出也就是仍然是第二个人胜。
当r≠0时
第一个人拿走r个物品这个时候问题就变成了r0时候的情况最后得出的结论是第一个人胜。 例题
HDU-1846 Brave Game
模板题
HDU-2188 悼念512汶川大地震遇难同胞——选拔志愿者
模板题不过要特判mn的情况。
HDU-2149 public sale 这道题可以作为理解当r≠0的时候第一个人取r件物品的情况。
#includecstring
#includecstdio
#includealgorithm
#includeiostream
#includevector
#includemap
#includestring
using namespace std;
int T,n,m;
int main()
{while(~scanf(%d%d,n,m)){if(mn){for(int in;im;i){printf(%d,i);if(i!m)printf( );}}else{if(n%(m1)0) printf(none);else{printf(%d,n%(m1));}}printf(\n);}return 0;
}威佐夫博奕Wythoff Game 有两堆石子石子数目分别为n和m,现在两个人轮流从两堆石子中拿石子每次拿时可以从一堆石子中拿走若干个也可以从两中拿走相同数量的石子拿走最后一个石子的人赢。 威佐夫博弈也是一个比较经典的神奇博弈在进行判断的时候提到了奇异局势对于这种局势先手必输。
下面我列举几种奇异局势
0,01,23,54,7610........
通过观察我们发现对于每一个奇异局势的第一个数字都是前面没有出现过的最小的正整数
比如3,5中的3前面两组是(0,1,2)那么最小的正整数是3。
对于这几种情况都是先手会输如果想看证明的话推荐这篇博客
https://blog.csdn.net/qq_34374664/article/details/52814983
下面就是玄学内容了目前不能推导后补
对于每组数据的第一个数它的值就等于这组数据的差值*1.618我算了算这一步要取整比如对于第四组数据3*1.6184.854int4.8544。
并且1.618刚好等于 ( sqrt(5.0) 1 ) / 2。
下面通过例题给出模板
例题HDU-1527 取石子游戏
模板题
#includecmath
#includecstdio
#includealgorithm
#includeiostream
using namespace std;
int n,m;
int main()
{while(cinnm){int x;if(nm){xn;nm;mx;}xm-n;if( (int)((sqrt(5.0)1)/2*x)n )printf(0\n);elseprintf(1\n);}return 0;
}HDU-2177 取(2堆)石子游戏 这道题相较于前面的模板题就有一点点难度了不过万变不离其宗接下来咱们就来谈谈这道题。
1、前面我们提到奇异局势的时候有提到对于每组数据的第一个数它的值就等于这组数据的差值*1.618换种思路就是说随着数据的展开它们之间的距离是逐渐变大的并且不同的距离对应不同的奇异局势好的现在知道了这一点那么接下来在跟随我去看看其他的思考点。
2、对于数据中的奇异数据一定满足的是先手是必输的对于一组数据我们想要让先手胜利的话只需满足第一个人在使用正确的方法取出部分石子后的数据满足奇异局势就行了也就是说在上面的模板的基础之上我们要对输出1必输的情况进行再讨论使得输出的数据中的每一组都是奇异局势。
3、我们知道我们取石子的时候是按照从第一个里面取出一部分或者在两堆石子里面同时取出相同的数量的石子来运算的那么我们就应该分两种情况进行讨论
①n和m之间的距离不变我们通过这个距离求出在当前距离下的奇异数据的第一个值并判断这个值是否小于n若这个值小于n的话就输出如果说这个值大于等于n的话就continue因为我们只能把石子取出不能放入。
②n和m之间的距离变小对于这种情况只能是m往左移动原因在①中已经提到我们通过枚举的方法找到符合条件的值因为枚举的点有可能在n的左边也有可能在n的右边所以我们要分情况进行讨论。
#includecmath
#includecstdio
#includealgorithm
#includeiostream
using namespace std;
int n,m;
int main()
{while(cinnm,nm){int xm-n;double sq ((sqrt(5.0)1)/2);if( (int)(sq*x)n )printf(0\n);else{printf(1\n);int x1(int)x*sq;//计算在(m-n)距离下对应的奇异数据的第一个值if(x1n)printf(%d %d\n,x1,x1(m-n));for(int i0;im;i){//从右往左枚举int x2m-i;if(x2n(int)((x2-n)*sq)n){printf(%d %d\n,n,x2);}else if(x2n(int)((n-x2)*sq)x2){printf(%d %d\n,x2,n);}}}}return 0;
}尼姆博奕Nimm Game 有3堆各若干个物品两个人轮流从某一堆取任意多的物品规定每次至少取1个多者不限最后取光者得胜。 分析
1、首先自己想一下就会发现只要最后剩两堆物品一样多(不为零)第三堆为零那面对这种局势的一方就必败
那我们用(a,b,c)表示某种局势首先(0,0,0)显然是必败态无论谁面对(0,0,0) 都必然失败第二种必败态是(0,n,n)自己在某一堆拿走kk ≤ n个物品不论k为多少对方只要在另一堆拿走k个物品最后自己都将面临(0,0,0)的局势必败。仔细分析一下(1,2,3)也是必败态无论自己如何拿接下来对手都可以把局势变为(0,n,n)的情形
那这种奇异局势有什么特点呢
也不知谁这么牛逼竟然能把这种局势和二进制联系在一起
这里说一种运算符号异或^,a^bababa为非a
我们用符号XOR表示这种运算这种运算和一般加法不同的一点是1 XOR 1 0。先看(1,2,3)的按位模2加的结果
1 二进制01
2 二进制10
3 二进制11 XOR
———————
0 二进制00 (注意不进位) 对于奇异局势(0,n,n)也一样结果也是0
任何奇异局势(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)这样的运算即可 2、尼姆博弈模型可以推广到有n堆若干个物品两个人轮流从某一堆取任意多的物品规定每次至少取一个多者不限最后取光者得胜。
这个游戏中的变量是堆数k和各堆的物品数N1N2……Nk。
对应的组合问题是确定先手获胜还是后手获胜以及两个游戏人应该如何取物品才能保证自己获胜 3、为了进一步理解Nim取物品游戏我们看看特殊情况。
如果游戏开始时只有一堆物品先手则通过取走所有的物品而获胜。现在设有2堆物品且物品数量分别为N1和N2。游戏者取得胜利并不在于N1和N2的值具体是多少而是取决于它们是否相等。
也就说两堆的策略我们有了现在我们如何从两堆的取子策略扩展到任意堆数中呢 首先回忆一下每个正整数都有对应的一个二进制数例如57(10) 111001(2) 即57(10)25242320。于是我们可以认为每一堆物品数由2的幂数的子堆组成。这样含有57枚物品大堆就能看成是分别由数量为25、24、23、20的各个子堆组成 现在考虑各大堆大小分别为N1N2……Nk的一般的Nim博弈。将每一个数Ni表示为其二进制数数的位数相等不等时在前面补0
N1 as…a1a0
N2 bs…b1b0
……
Nk ms…m1m0
如果每一种大小的子堆的个数都是偶数我们就称Nim博弈是平衡的而对应位相加是偶数的称为平衡位否则称为非平衡位。因此Nim博弈是平衡的当且仅当
as bs … ms 是偶数即as XOR bs XOR … XOR ms 0
……
a1 b1 … m1 是偶数即a1 XOR b1 XOR … XOR m1 0
a0 b0 … m0是偶数即a0 XOR b0 XOR … XOR m0 0 于是我们就能得出尼姆博弈中先手获胜策略
Bouton定理先手能够在非平衡尼姆博弈中取胜而后手能够在平衡的尼姆博弈中取胜。即状态(x1, x2, x3, …, xn)为P状态当且仅当x1 xor x2 xor x3 xor … xor xn 0。这样的操作也称为Nim和(Nim Sum)
我们以一个两堆物品的尼姆博弈作为试验。设游戏开始时游戏处于非平衡状态。这样先手就能通过一种取子方式使得他取子后留给后手的是一个平衡状态下的游戏接着无论后手如何取子再留给先手的一定是一个非平衡状态游戏如此反复进行当后手在最后一次平衡状态下取子后先手便能一次性取走所有的物品而获胜。而如果游戏开始时游戏牌平衡状态那根据上述方式取子最终后手能获 下面应用此获胜策略来考虑4堆的Nim博弈。其中各堆的大小分别为791215枚硬币。用二进制表示各数分别为011110011100和1111
于是可得到如下一表 由Nim博弈的平衡条件可知此游戏是一个非平衡状态的Nim博弈因此先手在按获胜策略一定能够取得最终的胜利。具体做法有多种先手可以从大小为12的堆中取走11枚硬币使得游戏达到平衡如下表 之后无论后手如何取子先手在取子后仍使得游戏达到平衡
同样的道理先手也可以选择大小为9的堆并取走5枚硬币而剩下4枚或者先手从大小为15的堆中取走13枚而留下2枚
归根结底 Nim博弈的关键在于游戏开始时游戏处于何种状态平衡或非平衡和先手是否能够按照取子游戏的获胜策略来进行游戏
当堆数大于2时我们看出Bouton定理依旧适用下面用数学归纳法证明 证明如果每堆都为0显然是P状态必败。下面验证P状态和N状态的后两个递推关系
一、每个N状态都可以一步到达P状态。
证明是构造性的。检查Nim和X的二进制表示中最左边一个1则随便挑一个该位为1的物品堆Y根据Nim和进行调整0变11变0即可。例如Nim和为100101011而其中有一堆为101110001。为了让Nim和变为0只需要让操作的物品数取操作前的物品数和Nim的异或即可
显然操作后物品数变小因此和合法的。设操作前其他堆的Nim和为Z则有Y xor Z X。操作后的Nim和为X xor Y xor Z X xor X 0是一个P状态
二、每个P状态必胜态都不可以一步到达P状态
由于只能改变一堆的物品不管修改它的哪一位Nim的对应位一定不为0不可能是P状态。
这样就证明了Bouton定理
实际解决
Nim博弈中如果规定最后取光者输情况是怎样的
初看起来问题要复杂很多因为不能主动拿了而要“躲着”拿以免拿到最后一个物品但对于Nim游戏来说几乎是一样的
首先按照普通规则一样的策略进行直到恰好有一个物品数大于1的堆x。在这样的情况下只需要把堆x中的物品拿得只剩1个物品或者拿完让对手面临奇数堆物品这奇数堆物品每堆恰好1个物品。这样的状态显然是必败的。由于你每次操作后需要保证Nim和为0因此不可能在你操作后首次出现“恰好有一个物品数大于1的堆”。新游戏得到了完美解决
上面这一小部分转自 https://www.cnblogs.com/jiangjun/archive/2012/11/01/2749937.html 例题
HDU-2176 取(m堆)石子游戏
这种从m堆里去石子的题目可以拆分成一个一个的单独的Nim博奕先说结论只要满足每一堆的异或为0就是先手必输后手必胜异或不为0则是先手获胜。 对于某个局面(a1,a2,…,an)若a1^ a2 ^ …^ an不为0一定存在某个合法的移动将ai改变成ai’后满足a1^ a2^ …^ ai’^ …^ an0(a1^a2^....^an0就代表必输如果说一定存在某个合法的移动使得必输的话这个地方就是必胜)。不妨设a1^ a2^ …^ ank则一定存在某个ai它的二进制表示在k的最高位上是1。因为只有这样才能使k的最高位为1。而且我们知道ai^ k ai因为只有ai和k的二进制最高位是1一异或肯定比ai小就像10000111所以此时我们ai^ k去替换ai此时原式就变成了a1^ a2^ … ^ ai^ … ^ an^ k k ^ k 0。
这个操作说明了我们可以通过一次操作使任何一个异或不为0的序列变成异或为0的序列而后手的操作一定会打破这种情况如此往复会得到全0的结果也就是先手会获得胜利。 类似的如果开始情况下异或为0 则先手会打破这种情况后手就会获得胜利。 至于题目中要求的操作我们可以通过什么提到的方式来实现即求出所有比ai小的ai^ k也就是替换后的结果。 #includecmath
#includecstdio
#includealgorithm
#includeiostream
using namespace std;
const int maxn2e5100;
int n,a[maxn];
int main()
{while(cinn,n){int sum0;for(int i1;in;i){scanf(%d,a[i]);sum^a[i];}if(sum0){printf(N0\n);}else{printf(Yes\n);for(int i1;in;i){if((sum^a[i])a[i]){printf(%d %d\n,a[i],sum^a[i]);}}}}return 0;
}HDU-1850 Being a Good Boy in Spring Festival
跟前面的例题几乎相同的一道题
#includecmath
#includecstdio
#includealgorithm
#includeiostream
using namespace std;
const int maxn2e5100;
int n,a[maxn];
int main()
{while(cinn,n){int sum0;for(int i1;in;i){scanf(%d,a[i]);sum^a[i];}if(sum0){printf(0\n);}else{int cont0;for(int i1;in;i){if((sum^a[i])a[i]){cont;}}printf(%d\n,cont);}}return 0;
}
