关键词:
威佐夫博弈
威佐夫博弈是一类经典的博弈问题
有两堆石子,两个顶尖聪明的人在玩游戏,每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子,不能取得人输,分析谁会获得胜利
博弈分析
威佐夫博弈不同于Nim游戏与巴什博奕,它的特殊之处在于不能将两堆石子分开分析。
前辈们在对该博弈游戏做了大量的探索之后最终找到了一些非常有意思的性质
下面的内容不想看的可以跳过直接看结论,其实也没啥乱用233,这部分就是为了拓宽视野的
定义先手必输的局势为奇异局势,前几个奇异局势为\\((0,0),(1,2),(3,5),(4,7),(6,10) \\dots\\)
假设\\((x,y)\\)为第\\(k\\)个奇异局势
性质:
- \\(x\\)为前\\(1 \\dots k\\)个奇异局势中没有出现过的最小正整数,\\(y=x+k\\)
打表找规律
- 任何一个自热数都包含在一个且仅有一个奇异局势中
感觉网上证的都不靠谱,那只好让本蒟蒻亲自下手喽
证明这个结论,我们只需要证明两点:(1)任意自然数都出现过(2)任意自然数仅出现一次
对于(1):反证法,设\\(v\\)这个数没有出现过,那么\\(v\\)可以做一个新的奇异局势的\\(x\\)
对于(2): 反证法
假设数\\(v\\)出现了两次,那么\\(v\\)一定不是所在奇异局势的\\(x\\)(\\(x\\)必须之前未出现)
那么\\(v\\)只能同时是两个奇异局势的\\(y\\),又因为任意一个奇异局势的差值不相同,因此\\(v\\)不可能出现两次
- 任何操作都会将奇异局势变为非奇异局势
若取走一堆中的石子,那么两对石子的差值会改变,必将成为非奇异局势
若同时取走,因为同一个差值只会对应一种奇异局势,必将成为非奇异局势
- 可以采取适当的方法将非奇异局势变为奇异局势
显然
结论
人们通过对上述性质的探索,同时结合Betty定理,给出了威佐夫博弈的重要结论
假设两堆石子为\\((x,y)\\)(其中\\(x<y\\))
那么先手必败,当且仅当
\\((y-x)*\\frac(\\sqrt5+1)2=x\\)
其中的\\(\\frac(\\sqrt5+1)2\\)实际就是\\(1.618\\),黄金分割数!怎么样,博弈论是不是很神奇?
证明的话,
首先你要会证明Betty定理,链接在上面,如果度娘的证明看不懂可以看这里
威佐夫博弈结论的话可以看这里
代码
题目
#include<cstdio>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
main()
int a,b;
scanf("%lld%lld",&a,&b);
if(a>b) swap(a,b);
int temp=abs(a-b);
int ans=temp*(1.0+sqrt(5.0))/2.0;
if(ans==a) printf("0");
else printf("1");
return 0;
例题
HDU 1527
题解
51NOD 1185
题解
巴仕博弈+威佐夫博弈(代码片段)
...1到m个石子,不能拿的人为败者,问谁会胜利巴什博奕是博弈论问题中基础的问题它是最简单的一种情形对应一种状态的博弈博弈分析如果有m+1个石子,那么先手必定无法取完全部,但后手可以取完剩下的部分,使得先手没有石... 查看详情
博弈论经典入门(代码片段)
文章目录博弈论常见模型必胜点和必败点的概念:必胜点和必败点的性质:巴什博弈斐波那契博弈威佐夫博弈尼姆博弈SG函数与SG定理博弈论博弈论,是经济学的一个分支,主要研究具有竞争或对抗性质的对象... 查看详情
基础博弈——威佐夫与尼姆不得不说的那些事(代码片段)
STEP1:首先了解规则与概念 威佐夫博弈(Wythoff‘sgame):有两堆各若干个物品,两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。 尼姆博弈(NimmGame)... 查看详情
博弈论——两人取子游戏与威佐夫博弈,隐藏在背后的黄金分割(代码片段)
...个关注今天是算法和数据结构专题第25篇文章,我们继续博弈论专题。在上一篇文章当中我们了解了最简单的巴什博奕,今天我们来看看另一个经典的博弈模型——威佐夫博弈。博弈论和机器学习有些类似,数学家们针对场景进... 查看详情
威佐夫博弈(代码片段)
博弈规则:有两堆各若干个物品,两个人轮流从某一堆取至少一个或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。a堆和b堆的个数用(a,b)表示奇异局势:面对的时候,就是输家,比如(0... 查看详情
hdu-5973gameoftakingstones(威佐夫博弈高精度)(代码片段)
题目描述:Twopeoplefacetwopilesofstonesandmakeagame.Theytaketurnstotakestones.Asgamerules,therearetwodifferentmethodsoftakingstones:Oneschemeisthatyoucantakeanynumberofstonesinanyonepilewhilethealternative 查看详情
hdu5973gameofgetingstone(威佐夫博弈)(代码片段)
Twopeoplefacetwopilesofstonesandmakeagame.Theytaketurnstotakestones.Asgamerules,therearetwodifferentmethodsoftakingstones:Oneschemeisthatyoucantakeanynumberofstonesinanyonepilewhilethealternativeistotakethesameamountofstonesatthesametimeintwopiles.Intheend,thefirstpersontakingallthestonesiswinner.No... 查看详情
hdu1527取石子游戏(威佐夫博弈)(代码片段)
取石子游戏TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):8514 AcceptedSubmission(s):4837ProblemDescription有两堆石子,数量任 查看详情
hdu1527取石子游戏(威佐夫博弈)(代码片段)
取石子游戏TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):9725 AcceptedSubmission(s):5605ProblemDescription有两堆石子,数量任 查看详情
[shoi2002]取石子游戏-威佐夫博弈(代码片段)
...都采取最好的策略,问最后你是胜者还是败者。Solution威佐夫博弈模板题如果一个局面是N必败局面,那么我们称它为奇异局面结论是,任意一个局面 查看详情
(博弈论高精度小数)51nod1185威佐夫游戏v2(代码片段)
有2堆石子。AB两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不会出现失误。给出2堆石子的数量,问最后谁能赢得比... 查看详情
博弈论威佐夫博弈
...获胜,请问先手还是后手胜? 对于学过一些博弈论基础的来说,我们需要找到那些能让先手必输的局势,那么由这些局势在规定范围内拓展的局势也是先手必输的局势(但在这里双方自由选取,不适用)。我们可以得... 查看详情
题解报告:hdu1527取石子游戏(威佐夫博弈)(代码片段)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1527ProblemDescription有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆... 查看详情
威佐夫博弈(代码片段)
有两堆各若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利。 我们用(ai,bi)表示当前局势,当前局势为以下情况者(证明略),先... 查看详情
hdu2177取(2堆)石子游戏(威佐夫博弈)(代码片段)
HDU2177取(2堆)石子游戏ProblemDescription有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石... 查看详情
博弈问题(巴什博弈威佐夫博弈尼姆博弈斐波拉契博弈)结论
巴什博弈有一堆n个石子从里面取,一次从里面取1~m个,最后取完者获胜。结论:如果n%(m+1)==0先手必败 n%(m+1)!=0为先手必胜。HDU4764#include<iostream>#include<algorithm>usingnamespacestd;intmain() intn,m; while(cin>>n>>m) 查看详情
博弈论-威佐夫博弈
理论分析问题:首先有两堆石子,博弈双方每次可以取一堆石子中的任意个,不能不取,或者取两堆石子中的相同个。先取完者赢。分析:首先我们根据条件来分析博弈中的奇异局势第一个(0,0),先手输,当游戏某一方面对... 查看详情
基础博弈(代码片段)
...流取,从一堆中取k个或者同时取k个,取光者胜。3.尼姆博弈论(NimmGame)n堆石头n堆石头,每次取一堆,无限制,取光者胜。 两个状态:P-positionP指的是Previous上一个N-positi 查看详情