博弈论试题集文档格式.docx
- 文档编号:6842746
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:51
- 大小:30.95KB
博弈论试题集文档格式.docx
《博弈论试题集文档格式.docx》由会员分享,可在线阅读,更多相关《博弈论试题集文档格式.docx(51页珍藏版)》请在冰点文库上搜索。
intmain()
{
intk;
longm,n;
cin>
>
k;
while(k--)
{
cin>
n>
m;
if(n%(m+1)==0)
cout<
<
"
Lose"
endl;
else
Win"
}
}
巴什博弈变形:
有两种解,依实际情况而定:
取石子(七)
1000
1
Yougth和Hrdv玩一个游戏,拿出n个石子摆成一圈,Yougth和Hrdv分别从其中取石子,谁先取完者胜,每次可以从中取一个或者相邻两个,Hrdv先取,输出胜利着的名字。
输入包括多组测试数据。
每组测试数据一个n,数据保证int范围内。
输出胜利者的名字。
3
Hrdv
Yougth
解一:
cstdio>
intn;
while(~scanf("
%d"
&
n))
printf(n>
=3?
Yougth\n"
:
Hrdv\n"
);
return0;
}
解二:
3的倍数的是Yougth嬴
inta;
while(cin>
a)
if(a%3!
=0)
cout<
Hrdv"
elsecout<
Yougth"
return0;
尼姆博弈基本思想:
两人从n堆物品中取任意个,先取完者胜。
即将n堆物品的数量异或,得到的值如果为0,则先手败,反之先手胜。
如果要求先手在胜的条件下,到奇异局势的方法数,则判断异或的值与每一堆原值异或后(结果应该表示该堆没有参加异或时的异或值)与原值比较大小,
如果小于,则方法数加一。
且对应的方法后,该堆的数目应变为异或的值与每一堆原值异或的值。
取石子
(二)
5
小王喜欢与同事玩一些小游戏,今天他们选择了玩取石子。
游戏规则如下:
共有N堆石子,已知每堆中石子的数量,并且规定好每堆石子最多可以取的石子数(最少取1颗)。
两个人轮流取子,每次只能选择N堆石子中的一堆,取一定数量的石子(最少取一个),并且取的石子数量不能多于该堆石子规定好的最多取子数,等哪个人无法取子时就表示此人输掉了游戏。
假设每次都是小王先取石子,并且游戏双方都绝对聪明,现在给你石子的堆数、每堆石子的数量和每堆石子规定的单次取子上限,请判断出小王能否获胜。
第一行是一个整数T表示测试数据的组数(T<
100)
每组测试数据的第一行是一个整数N(1<
N<
100),表示共有N堆石子,随后的N行每行表示一堆石子,这N行中每行有两个数整数m,n表示该堆石子共有m个石子,该堆石子每次最多取n个。
(0<
=m,n<
=2^31)
对于每组测试数据,输出Win表示小王可以获胜,输出Lose表示小王必然会败。
11
提示
注意下面一组测试数据
11
22
正确的结果应该是Win
因为小王会先从第二堆石子中取一个石子,使状态变为
12
这种状态下,无论对方怎么取,小王都能获胜。
最优解
intmain(){
intT;
scanf("
T);
while(T--){
intm,n,g,sum=0;
scanf("
g);
while(g--){scanf("
%d%d"
m,&
n);
sum^=m%(n+1);
puts(sum?
一般解:
#include<
boolHandleEachCase();
intiCaseCount;
cin>
iCaseCount;
while(iCaseCount--){
if(HandleEachCase()){
}else{
boolHandleEachCase(){
longlongmagic=0;
longlongiCount;
longlongm,n;
iCount;
for(inti=0;
i<
iCount;
++i){
m>
n;
m%=(n+1);
magic^=m;
returnmagic!
=0;
取石子(六)
最近TopCoder的PIAOYI和HRDV很无聊,于是就想了一个游戏,游戏是这样的:
有n堆石子,两个人轮流从其中某一堆中任意取走一定的石子,最后不能取的为输家,注意:
每次只能从一堆取任意个,可以取完这堆,但不能不取。
假设PIAOYI先取石子,请你帮他判断他是否能赢(假设他们取的过程中不发生失误,他们足够聪明
)。
第一行输入n,代表有n组测试数据(n<
=10000)
以下每组测试数据包含两行:
第一行:
包含一个整数m,代表本组测试数据有m(m<
=1000)堆石子;
:
第二行:
包含m个整数Ai(Ai<
=100),分别代表第i堆石子的数量。
若PIAOYI赢输出“PIAOYI”,否则输出“HRDV”注意每组结果占一行。
。
3811
510
voidin(int&
charch;
while((ch=getchar())<
'
0'
||ch>
9'
for(a=0;
ch>
='
&
ch<
;
ch=getchar())a=a*10+ch-'
in(T);
while(T--)
intn;
in(n);
intans=0;
for(inti=0;
i!
=n;
++i)
{
intb;
in(b);
ans^=b;
}
if(ans)puts("
PIAOYI"
elseputs("
HRDV"
}return0;
取石子(三)
6
共有N堆石子,已知每堆中石子的数量,两个人轮流取子,每次只能选择N堆石子中的一堆,取一定数量的石子(最少取一个),取过子之后,还可以将该堆石子中剩下的任意多个石子中随意选取几个放到其它的任意一堆或几堆上。
等哪个人无法取子时就表示此人输掉了游戏。
注意,一堆石子没有子之后,就不能再往此处放石子了。
假设每次都是小王先取石子,并且游戏双方都绝对聪明,现在给你石子的堆数、每堆石子的数量,请判断出小王能否获胜。
例如:
如果最开始有4堆石子,石子个数分别为3142,而小王想决定要先拿走第三堆石子中的两个石子(石子堆状态变为3122),然后他可以使石子堆达到的状态有以下几种:
3122(不再移动石子)
4112(移动到第一堆一个)
3212(移动到第二堆一个)
3113(移动到第四堆一个)
5102(全部移动到第一堆)
3302(全部移动到第二堆)
3104(全部移动到最后)
可能有多组测试数据(测试数据组数不超过1000)
每组测试数据的第一行是一个整数,表示N(1<
=10)
第二行是N个整数分别表示该堆石子中石子的数量。
(每堆石子数目不超过100)
当输入的N为0时,表示输入结束
213
cstring>
cstdlib>
while(HandleEachCase()){
刚刚开始的时候,如果已经两两配对了,那么先拿的输了,否则,选拿的可以把最大的动一下手脚,使剩下的两两配对,且每一对的数目相同.
boolok(intstone[])
for(inti=0;
=110;
i++)
if(stone[i]&
1)returntrue;
returnfalse;
intstone[110];
intn,m;
while(cin>
n&
n)
memset(stone,0,sizeof(stone));
while(n--)
cin>
stone[m]++;
cout<
(ok(stone)?
)<
}
威佐夫博奕(WythoffGame):
有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
这种情况下是颇为复杂的。
我们用(ak,bk)(ak≤bk,k=0,1,2,...,n)表示两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们称为奇异局势。
前几个奇异局势是:
(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而bk=ak+k,奇异局势有如下三条性质:
1。
任何自然数都包含在一个且仅有一个奇异局势中。
由于ak是未在前面出现过的最小自然数,所以有ak>
ak-1,而bk=ak+k>
ak-1+k-1=bk-1>
ak-1。
所以性质1。
成立。
2。
任意操作都可将奇异局势变为非奇异局势。
事实上,若只改变奇异局势(ak,bk)的某一个分量,那么另一个分量不可能在其他奇异局势中,所以必然是非奇异局势。
如果使(ak,bk)的两个分量同时减少,则由于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势。
3。
采用适当的方法,可以将非奇异局势变为奇异局势。
假设面对的局势是(a,b),若b=a,则同时从两堆中取走a个物体,就变为了奇异局势(0,0);
如果a=ak,b>
bk,那么,取走b
-bk个物体,即变为奇异局势;
如果a=ak,
b<
bk,则同时从两堆中拿走ak-ab-ak个物体,变为奇异局势(ab-ak,ab-ak+b-ak);
如果a>
ak,b=ak+k,则从第一堆中拿走多余的数量a-ak即可;
如果a<
ak,b=ak+k,分两种情况,第一种,a=aj(j<
k),从第二堆里面拿走b-bj即可;
第二种,a=bj(j<
k),从第二堆里面拿走b-aj即可。
从如上性质可知,两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜;
反之,则后拿者取胜。
那么任给一个局势(a,b),怎样判断它是不是奇异局势呢?
我们有如下公式:
ak=[k(1+√5)/2],bk=ak+k
(k=0,1,2,...,n方括号表示取整函数)奇妙的是其中出现了黄金分割数(1+√5)/2=1。
618...,因此,由ak,bk组成的矩形近似为黄金矩形,由于2/(1+√5)=(√5-1)/2,可以先求出j=[a(√5-1)/2],若a=[j(1+√5)/2],那么a=aj,bj=aj+j,若不等于,那么a=aj+1,bj+1=aj+1+j+1,若都不是,那么就不是奇异局势。
然后再按照上述法则进行,一定会遇到奇异
局势。
取石子(四)
4
有两堆石子,数量任意,可以不同。
游戏开始由两个人轮流取石子。
游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;
二是可以在两堆中同时取走相同数量的石子。
最后把石子全部取完者为胜者。
现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。
输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,000。
输出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。
21
84
47
cmath>
{
intm,n;
n)
if(m>
inttemp;
temp=m;
m=n;
n=temp;
intk=n-m;
intdata=floor(k*+sqrt)/;
if(data==m)
0<
1<
WythoffGame
最近ZKC同学在学博弈,学到了一个伟大的博弈问题--威佐夫博弈。
相信大家都学过了吧?
没学过?
没问题。
我将要为你讲述一下这个伟大的博弈问题。
游戏规定,每次有两种不同的取法:
一是可以在任意的一堆中取走任意多的石子;
我们今天要做的是求前n个必败态。
什么是必败态?
比如我们把(a,b)称为一种状态,a,b分别为两堆石子中所剩的数目。
如果a=0,b=0,我们说该种状态为必败态,因为我不能再进行游戏,即使是可以进行,那也是必败的,你知道,游戏的我们都是非常聪明的。
(0,0)(1,2)(3,5)...都是必败态,我们今天要做的就是求前n个必败态。
不会?
好吧!
我再告诉你:
假设第n个必败态为(a,b)a为前n-1个必败态中没有出现的最小自然数,b=a+n。
这下大家应该明白了吧。
好吧,我们的任务就的要前n个必败态。
规定第0个必败态为(0,0)。
多组数据。
输入为一个数n(0<
=n<
=100000)。
按照要求求出前n个必败态。
输出格式看下面样例。
(0,0)(1,2)(3,5)(4,7)
(0,0)(1,2)
提示
注意:
每种情况中间没有空格
typedefstructNode
inta,b;
}N;
Nres[100001];
voidinit()
res[0].a=0;
res[0].b=0;
for(inti=1;
i<
100001;
res[i].a=(1+sqrt(5))*i/2;
res[i].b=res[i].a+i;
intn;
init();
while(scanf("
n)!
=EOF)
printf("
(%d,%d)"
res[i].a,res[i].b);
printf("
\n"
本人自己写的代码:
intn,k,b,a[100001],i,m=0;
a[0]=0;
if(n<
=m)
for(k=0;
k<
k++)
{
printf("
a[k],a[k]+k);
}
}else
a[0],a[0]);
for(k=1;
b=a[k-1]+1;
for(i=k-1;
i>
=0;
i--)
{
if(b==(a[i]+i))
{
b++;
}elseif(b>
(a[i]+i))
break;
}
}
a[k]=b;
m=n;
取石子(八)
如果你胜,你第1次怎样取子?
输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000。
a=b=0退出。
输出也有若干行,如果最后你是败者,则为0,反之,输出1,并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<
=y。
如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜,先输出取走相同数量的石子的情况,假如取一堆的有多种情况,先输出从石子多的一堆中取的情况,且要求输出结果保证第二个值不小于第一个值。
12
57
00
35
algorithm>
inta,b,temp,temp2,k,i;
a,&
b),a+b)
if(a>
b)
swap(a,b);
k=b-a;
temp=k*+sqrt)/;
if(a==temp)先手不能在第一次把所有的石子取完;
2.之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。
约定取走最后一个石子的人为赢家,求必败态。
(转)分析:
n=2时输出second;
n=3时也是输出second;
n=4时,第一个人想获胜就必须先拿1个,这时剩余的石子数为3,此时无论第二个人如何取,第一个人都能赢,输出first;
n=5时,first不可能获胜,因为他取2时,second直接取掉剩下的3个就会获胜,当他取1时,这样就变成了n为4的情形,所以输出的是second;
n=6时,first只要去掉1个,就可以让局势变成n为5的情形,所以输出的是first;
n=7时,first取掉2个,局势变成n为5的情形,故first赢,所以输出的是first;
n=8时,当first取1的时候,局势变为7的情形,第二个人可赢,first取2的时候,局势变成n为6得到情形,也是第二个人赢,取3的时候,second直接取掉剩下的5个,所以n=8时,输出的是second;
…………
从上面的分析可以看出,n为2、3、5、8时,这些都是输出second,即必败点,仔细的人会发现这些满足斐波那契数的规律,可以推断1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 博弈论 试题