OpenJudge计算概论-取石子游戏

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
");
        else printf("lose
");
        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
");
        else printf("lose
");
        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);
}