信息学奥赛一本通T1218：搜索与回溯算法（DFS） 取石子游戏

【题目描述】有两堆石子,两个人轮流去取。每次取的时候,只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍，最后谁能够把一堆石子取空谁就算赢。比如初始的时候两堆石子的数目是25和7。25 7 --> 11 7 --> 4 7 --> 4 3 --> 1 3 --> 1 0最后选手1（先取的）获胜，在取的过程中选手2都只有唯一的一种取法。给定初始时石子

信息学奥赛一本通T1218：取石子游戏

【题目描述】

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

比如初始的时候两堆石子的数目是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

思路：使用欧几里得辗转相除法即可

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 101
using namespace std;
int main()
{
    int m,n;
    int temp;
    int flag;
    while(scanf("%d%d",&m,&n)!=EOF&&m&&n)
    {
        flag=1;
        if(m<n)
        {
            temp=m;
            m=n;
            n=temp;
        }
        while(m/n==1)
        {
            temp=m;
            m=n;
            n=temp%n;
            flag=-flag;
        }
        if(flag==1)
            cout<<"win"<<endl;
        else
            cout<<"lose"<<endl;
    }
    return 0;
}

 

信息学奥赛一本通T1218：搜索与回溯算法（DFS） 取石子游戏 归属于 搜索与回溯算法（DFS），更多同类题解源程序见：搜索与回溯算法（DFS） 和 取石子游戏

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章

轩爸

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！