ZJU 1003Crashing Ballon

本文主要是介绍ZJU 1003Crashing Ballon，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用回溯搜索，从2开始一直搜索因数到100。设获胜者的分数为m，挑战者的分数为n(m>n)，当前搜索到的因数为p，flag1为是否两人分数能分解成一合法形式，flag2为挑战者的分数是否符合要求。搜索函数为f(m,   n,   p)，初始时flag1   =   flag2   =   FALSE。由于每个因数只能出现一次，所以：如果p|m，则f(m   DIV   p,   n,   p+1)，如果p|n，则f(m,   n   DIV   p,   p+1)。还有可能不分解出因数p，所以当p<m或p<n时，f(m,   n,   p+1)。当搜索到m=1且n=1时，说明存在一种没有出现相同因数的分解，设flag1为TRUE。如果发现n=1，则挑战者的分数可以分解，符合要求，设为TRUE。最后的分析表格同上表。优化：flag1和flag2的初始状态都是FALSE，我们由上面的分析可以发现，flag1只要变成TRUE，最后的答案也就定下来了，于是，当flag1发生改变时就可以退出搜索了。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
bool a1,b1;//低分获胜的回溯结果就是b == 1，a已经不可能为1.
int judge(int a,int b,int p)
{
if(a1)
return 0;
if(a == 1&&b == 1)
{
a1=true ;
return 0;
}
if(b == 1)
b1=true ;
while(p>1)
{
if(a%p==0)judge(a/p,b,p-1);
if(b%p==0)judge(a,b/p,p-1);
p--;
}
return 0;
}
int main()
{
int a,b;
while(cin>>a>>b)
{
a1=b1=false;
if(a<b)
swap(a,b);
judge(a,b,100);
if(b1&&!a1)
cout<<b<<endl;
else
cout<<a<<endl;
}
return 0;
}

这篇关于ZJU 1003Crashing Ballon的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---