概述
有两堆扑克牌，数量任意（均大于0），可以不同。两人开始博弈，轮流抽取扑克牌。规定每次取牌有两种方式，第一种方式是任选一堆扑克牌，并从中取走任意张（大于0）；第二种是在两堆扑克牌中同时取走相同张数（大于0）的牌，每次取牌时必须选择一种方式，最后把牌全部取完的一方胜利。现在给出初始两堆扑克牌的数目，假设博弈的两人都绝顶聪明，问是先取者胜还是后取者胜。
题同 hdu 1527取石子游戏(威佐夫博奕)
威佐夫博奕
（
Wythoff
Game
）
：有两堆各若干个物品，两个人轮流从某一堆或同时
从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况下是颇为复杂的。我们用（
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
，若都不是，那么就不是奇异局势。然后
再按照上述法则进行，一定会遇到奇异
局势。
威佐夫博奕
（
Wythoff
Game
）
：有两堆各若干个物品，两个人轮流从某一堆或同时
从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况下是颇为复杂的。我们用（
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
，若都不是，那么就不是奇异局势。然后
再按照上述法则进行，一定会遇到奇异
局势。
威佐夫博奕（Wythoff Game）有两堆各若干个物品，两个人轮流从某一堆或同时 从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况下是颇为复杂的。我们用（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，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。
#include<stdio.h>
#include<math.h>
int main(){
int a,b,k,m,t;
while(scanf("%d%d",&a,&b)!=EOF){
if(a>b){
t=a;
a=b;
b=t;
}
k=b-a;
m=(int)((sqrt(5.0)+1)*k/2);
if(m!=a)
printf("The first one will win!n");
else
printf("The second one will win!n");
}
return 0;
}参考文档：http://wenku.baidu.com/link?url=lGGcIh7HSkSTTtipOaX1r2Syp3my4a_v4B8v1uR030qYlJcRc5G3IteIIgS6Zyhw_A5ozPihJeM9Vj_6bz0eG8KFmbJ4StVI0wYNuMAvzAe
最后
以上就是安详路灯为你收集整理的BJFU 1010 博弈 解题报告的全部内容，希望文章能够帮你解决BJFU 1010 博弈 解题报告所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复