CUMTOJ数据结构实验内容1-2 problemE

1103 problem 欧几里得游戏 C++

题目描述

小明和小红在玩欧几里得游戏。他们从两个自然数开始，第一个玩家小明，从两个数的较大数中减去较小数的尽可能大的正整数倍，只要差为非负即可。然后，第二个玩家小红，对得到的两个数进行同样的操作，然后又是小明。就这样轮流进行游戏，直至某个玩家将较大数减去较小数的某个倍数之后差为0为止，此时游戏结束，该玩家就是胜利者。

输入

输入包含多组测试数据。每组输入两个正整数，表示游戏一开始的两个数，游戏总是小明先开始。
当输入两个0的时候，输入结束。

输出

对于每组输入，输出最后的胜者，我们认为他们两个都是顶尖高手，每一步游戏都做出了最佳的选择。
具体输出格式见输出样例。

样例输入

34 12
15 24
0 0

样例输出

xiaoming wins
xiaohong wins

程序如下

#include<iostream>
using namespace std;
int main()
{
    int a,b,k,t;
    while(cin>>a>>b,a!=0||b!=0)
    {
        k=1;
        if(a==b)
            cout<<"xiaoming wins"<<endl;    
        else
        {
            while(a!=b)
            {
                if(a<b)//如果a<b，就交换ab值
                {
                    t=a;
                    a=b;
                    b=t;
                }
                k++;
                if(a/b!=1)
                {
                    break;
                }
                a=a%b;
            }
            if(k%2==1)
                cout<<"xiaohong wins"<<endl;
            else
                cout<<"xiaoming wins"<<endl;
        }
    }
    return 0;
}