开发者社区> 华山青竹> 正文

OpenJudge计算概论-取石子游戏

简介: OpenJudge计算概论-取石子游戏【函数递归练习】 /*====================================================================== 取石子游戏 总时间限制:  1000ms       内存限制: 65536kB 描述 有两堆石子,两个人轮流去取.
+关注继续查看

OpenJudge计算概论-取石子游戏【函数递归练习】

/*======================================================================

取石子游戏

总时间限制:  1000ms       内存限制: 65536kB

描述

有两堆石子,两个人轮流去取.每次取的时候,只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍.最后谁能够把一堆石子取空谁就算赢. 
比如初始的时候两堆石子的数目是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] >= 2则先手必胜,如果[a/b]<2,那么先手只有唯一的一种取法.
[a/b]表示a除以b取整后的值.

========================================================================*/

解析:(《数学与程序设计》东南大学出版社page5例题1-2 欧几里德的游戏)

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

游戏过程的各个状态

辗转相除法的过程

属于哪一局

所属情况

50  18

50/18=2……14

第1局初状态

第一种

32  18

 

第1局末状态

14  18

18/14=1……4

第2局初状态

(也是末状态)

第二种

14  4

14/4=3……2

第3局初始状态

第一种

10  4

 

第3局中间状态

6  4

 

第3局末状态

2  4

4/2=2……0

第4局

 

我们可以把一步辗转相除以及它与下一步辗转相除法之间的游戏状态称作一局,辗转相除的被除数和除数实际上对应了每一局的初状态。显然,每一局的初状态是游戏中必然出现的,而且最后一局只有一个状态,面临最后一局初状态的人就赢得了胜利。

因此,本题对的大致想法是:尽量让自己能取得每一局的初状态,让对手取得每一局(除最后一局)的末状态。下面分两种情况来具体说说这个想法的实现:

第一种情况:先举一个例子A=32,B=14,A和B的辗转相除法过程如下:

32/14=2……4

14/4=3……2

4/2=2……0

这种情况的特点是:每一步相除所得的商都大于1,即对于每一局的初状态(A,B),A>B,都满足:A/B>1。对这种情况,我们的策略是取走(A/B-1)*B,这样就得到新状态(A  mod  B+B,B),接下来,对手就没有选择,只能取走B,剩下(A  mod  B,B),而这就是下一句的初状态,这样就保证下一局的初状态肯定由自己取,这种情况下先取者必胜。

第二种情况:某一局的初状态满足A/B=1,即这一局只有一个状态,自己取完之后下一局的初状态必然落在对方手里。以下是这种情况的一般性表述:存在连续的若干局Pi(Ai,Bi),……Pj(Aj,Bj),i+1<j,Ai/Bi>1,且对于任意一局Pk(Ak,Bk),i<k<j,均满足Ak/Bk=1。如果j-i是奇数,则Pj和Pi的初始状态的持有人是相同的,如果j-i是偶数则不同。因此,如果出现j-i为偶数,就有必要在Pi局中把当局的状态一次性全部取完,即把下一局的初状态拱手相让,这样就保证在Pj局中再次拿到初状态。

总之,首先拿到A/B>1状态的人,总能根据两种情况作出正确的选择,从而在最后一局拿到初状态。因此,首先拿到A/B>1状态的人是必胜的,但如果出现从初状态开始,每局都是A/B=1,如A=24,B=15,则要根据这样的局数多少来判断输赢。

解决代码如下:

#include<stdio.h>
int main()
{
    int a,b;
    int t,f,c;
    scanf("%d%d",&a,&b);
    while(a!=0&&b!=0)
    {
        if(a<b)
        {
            t=a;a=b;b=t;
        }
        f=1;//1表示选手赢,-1表示选手1输。
        while((c=a/b)==1&&(a%b!=0))
        {
            t=a%b;
            a=b;
            b=t;
            f=-f;
        }
        if(f==1)  printf("win\n");
        else printf("lose\n");
        scanf("%d%d",&a,&b);
    }
    return 0;
}

其实也可以用递归来做,但其实递归没有上面这个这么好理解:

#include<stdio.h>
int f;
int fun(int a,int b);
int main()
{
    int a,b;
    int t,c;
    scanf("%d%d",&a,&b);
    while(a!=0&&b!=0)
    {
        if(a<b)
        {
            t=a;a=b;b=t;
        }
        f=1;//1表示选手赢,-1表示选手1输。
        f=fun(a,b);
        if(f==1)  printf("win\n");
        else printf("lose\n");
        scanf("%d%d",&a,&b);
    }
    return 0;
}
int fun(int a,int b)
{
    int c;
    if((c=a/b)>1||(a%b==0))
        return f;
    else
    {
        f=-f;
    }    return fun(b,a%b);
}

 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19082 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
28301 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22183 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15766 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20277 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23541 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14878 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载