当前位置: 首页 > >

【一本通】1218:取石子游戏(博弈论)

发布时间:


题目描述:

有两堆石子,两个人轮流去取。每次取的时候,只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍,最后谁能够把一堆石子取空谁就算赢。


比如初始的时候两堆石子的数目是25和7。


?


25 7-->11 7-->4 7-->4 3-->1 3-->1 0
?选手1取?选手2取?选手1取?选手2取?选手1取

?


最后选手1(先取的)获胜,在取的过程中选手2都只有唯一的一种取法。


给定初始时石子的数目,如果两个人都采取最优策略,请问先手能否获胜。


?


【输入】

输入包含多数数据。每组数据一行,包含两个正整数a和b,表示初始时石子的数目。


输入以两个0表示结束。


?


【输出】

如果先手胜,输出"win",否则输出"lose"


【输入样例】

34 12
15 24
0 0

【输出样例】

win
lose


解题思路:

一看”取石子“,第一反应就是博弈论。但是这与博弈论经典的取石子问题不一样,取石子的数量要求一定是另一堆的整数倍(也就是在潜规则中定义:只能在大的那一堆取)。不过没关系,有我陪你慢慢推(哈哈哈哈~~~)


由于假定取石子的游戏两方智商都无限高,所以要想赢,就只能给对方剩一条一定会输的路,这样无论他智商再高,他都只有这一条路、没有别的选择使得他赢。


所以博弈论解题的第一步都往往是找出这样一个注定会输掉的境地。


根据境地“没有别的选择使得他赢”的定义回到这一题


发现:存在石堆A和石堆B,A>B? 且? A?/ B =1……C 时 由于要求是另一堆的整倍数,取A堆的石子就只有一种方法??取B个石子。这就是所谓“没有别的选择”。


但是“没有别的选择”不代表一定会输掉,那什么情况下才会达成“没有别的选择并且输掉”呢?


这道题会使人想到辗转相除法。其实,辗转相除法的除数和余数所形成的各种状态都会在游戏过程中出现。


笔者精心挑选了两个数:21 13,这两个数辗转相除的过程如下


21 / 13=1……8 (先手取后,剩下:8? 13)


13 / 8=1……5 (后手取后,剩下:8? ?5)


8 / 5=1……3 (先手取后 ,剩下:3? ?5)


5 / 3=1……2 (后手取后,剩下:3? ? 2)


3 / 2=1……1 (先手取后,剩下:1? ? 2)


2 / 1=2……0 (后手取后,剩下:1? ??0【取完一堆】)


我们发现前5条式子都符合 A?/ B =1……C 所以两方在取石子的时候都“没有别的选择”,而取到最后一条式子的人就能赢得这场比赛,对于这两堆石子,先手必输。所以我们发现,奇数个连续的 A?/ B =1……C 式子 会导致先手必输,偶数个则保证先手必赢。


那我们怎么才能创造出奇数个连续的 A?/ B =1……C 式子给对方呢?


第一种:你也没有办法,刚好从开始就剩下偶数个连续的 A?/ B =1……C 式子(很欠揍耶~)


第二种:你在开始遇到的是A?/ B =n……C 式子(n不等于1),那么你就可以自由操控全局了!


为什么?因为??


如果你在后面遇到了奇数个 A?/ B =1……C式子,那你直接将n个B拿走了就好,这样在下轮作为先手的对方必输。


如果你在后面遇到了偶数个 A?/ B =1……C式子,那你就只需要拿走(n-1)个B就好了,这样本条式子就会变成A?/ B =1……C,加上后面的偶数个A?/ B =1……C式子,对手就会面对奇数个A?/ B =1……C。


发现没有!!只要你一遇到一个A?/ B =n……C 式子(n不等于1),你就赢定了!!!


这就是为什么我在前文一直强调是连续的 A?/ B =1……C 式子。


这样我们就只需要判断,谁会第一个遇到A?/ B =n……C 式子,谁就必定会赢得本场比赛。完证!!


?


附上代码

#include
#include
#include
using namespace std;
int main()
{
// freopen("d9.in","r",stdin);
// freopen("d9.out","w",stdout);
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0 && m==0)break;
if(n if(n/m>=2){printf("win
");continue;}
int i=0;
while(n/m==1)
{
int x=n;n=m;m=x%n;
i++;
}
if(i%2==1)printf("lose
");
else printf("win
");
}
return 0;
}

?



友情链接: