取石子游戏-题解

题目：普及难度 DFS算法(类似模拟)

题解目录

• 题目分析

• 辨析-题中"最优策略"

• 输赢判断

• 代码实现

题目分析

a,b两堆石子,两个人(先后手)去取，每次只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍

最后能把a或b中石子取完的人获胜(a=0||b=0)

要求输出先手能否获胜

辨析-题中"最优策略"

题中说两个人都采取最优策略

那么此处的最优策略是什么呢？

由前面的题目分析可得，最后能把a或b中石子取完的人获胜

因此这两个人若都采用最优策略的话，肯定是希望在自己的回合时能够一次性取完石子或者是取尽可能多的石子

又因为每次只能取较少的那堆石子数目的整数倍

所以取的一次"最优策略"取的上限是a%b (a>b)

先后手输赢判断

判断输赢的话题目中是给了提示的

设石子数目为(a,b),且a>=b,如果[a/b]>=2则先手必胜，否则先手只有唯一的一种取法

所以就有了输赢的条件

1.[a/b]>=2

2.a=0或b=0 (由1可推)

3.a=b (由1可推)

对于判断先后手可以在dfs模拟时设虚参step

起始时step=1 (先手) 当满足上述所说的输赢条件时
判断step为奇数还是偶数
如果为奇数则是正手胜利，否则相反

代码实现

#include <bits/stdc++.h>
using namespace std;
int a,b;
bool flag;
void dfs(int a,int b,int step){
	if(b>a) swap(a,b);//保证a始终大于b
	double ans=a*1.0/b;
	if(ans>=2||(a==0||b==0)||a==b){
		if(step%2==1){
			flag=1;
		}return ;
	}
	dfs(a%b,b,step+=1); //因为“最优策略”所以每一次要尽可能取完 a%b
}
int main(){
	cin>>a>>b;
	while(a!=0&&b!=0){
		dfs(a,b,1);
		if(flag) {cout<<"win"<<endl;}
		else {cout<<"lose"<<endl;}
		
		cout<<"建设良好ACGO社区,拒绝一味题解抄袭"<<endl;
		
		cin>>a>>b;
		flag=0;
	}
	return 0;
}

首发题解，如有不对，尽情指正awa