信息学奥赛一本通 1218：取石子游戏 搜索与回溯算法
假设石子数目为(a,b)且a >= b,如果[a/b] >= 2则先手必胜,如果[a/b]
·
1218：取石子游戏
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
有两堆石子,两个人轮流去取。每次取的时候,只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍，最后谁能够把一堆石子取空谁就算赢。
比如初始的时候两堆石子的数目是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取整后的值。
解析：深度优先搜索，详见代码：
#include<bits/stdc++.h>
using namespace std;
int a,b;
bool f(int a,int b,bool s){//s表示是否为选手1
if (b>a){
swap(a,b);
}
if (a%b==0){//当前选手直接赢了
return s;//如果是选手1，返回true，否则返回false
}
if (a/b>=2){//如果有控制谁进入下一轮的控制权，也赢了
return s;//如果是选手1，返回true，否则返回false
}
return f(a%b,b,!s);//进入下一轮
}
int main()
{
cin>>a>>b;
while(a!=0&&b!=0){
if (f(a,b,true)==true){
cout<<"win"<<endl;
}else{
cout<<"lose"<<endl;
}
cin>>a>>b;
}
return 0;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
6
0- 0
已为社区贡献20条内容
所有评论(0)