给出一个分数，比如19/45，把它写成若干个形如1/Ri的分数的和的形式，比如19/45=1/5+1/6+1/18，要求分母不能重复使用并且使用的分数的个数最少。（如果有多组个数相同的解，最后的分数的分母越小越好，这对于题目来说是次要的。）
1、分母从小到大搜索
为了避免重复搜索
2、使用迭代加深搜索
求“步骤数最少”这类问题，基本上有两种似乎：广搜、迭代加深搜索。对于这道题来说，如果广搜将永远得不到结果，分母可以无限大！但是迭代加深搜索就比较好，虽然做了许多重复工作，但状态空间至少被限制住了。如果当前正在枚举的分母，使得接下来的选择即使每次都选择最大，达到最大深度的时候也不可能达到目标分数，那么当前正在枚举的分母及比它还大的分母，都不需要枚举了。这样可以给分母确定一个上界。另外，已经得到的结果加上当前枚举的分母对应的分数，要小于等于目标分数，这样给分母确定了一个下界（可以在O(1)的复杂度内确定这个下界）。
在下面的代码中，因为确定上下界都使用了浮点运算，最终还是需要把当前结果和目标结果比较。
浮点运算～真让人纠结的东西！
以下是我的代码：
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int gcd(int a,int b)
{
for(int t=a%b;t;a=b,b=t,t=a%b); return b;
}
struct Type
{
Type():a_(0),b_(1) {}
Type(int a,int b):a_(a),b_(b) {}
int a_,b_;
};
Type operator+(const Type &a,const Type &b)
{
Type re(a.a_*b.b_+a.b_*b.a_,a.b_*b.b_);
int t(gcd(re.a_,re.b_));
re.a_/=t;
re.b_/=t;
return re;
}
bool operator==(const Type &a,const Type &b)
{
return (a.a_*b.b_==b.a_*a.b_);
}
Type target;
int ans,r[10000],t[10000];
bool found;
void dfs(const int &depth,const int &last,const Type &now)
{
if(depth>ans)
{
if(now==target)
{
if(found)
{
bool cover(false);
for(int i=ans;i>=1;i--)
if(r[i]>t[i])
{
cover=true;
break;
}
else if(r[i]<t[i])
break;
if(cover)
for(int i=1;i<=ans;i++)
r[i]=t[i];
}
else
{
for(int i=1;i<=ans;i++)
r[i]=t[i];
found=true;
}
}
return;
}
for(int i=max(last+1,(int)ceil((double)(target.b_*now.b_)/(target.a_*now.b_-target.b_*now.a_))); ;i++)
{
Type news(now+Type(1,i));
if(depth+(int)ceil((double)(target.a_*news.b_-target.b_*news.a_)*(i+1)/(target.b_*news.b_))>ans)
break;
t[depth]=i;
dfs(depth+1,i,news);
}
}
int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
while(scanf("%d%d",&target.a_,&target.b_)==2)
{
found=false;
for(ans=1; ;ans++)
{
dfs(1,0,Type());
if(found)
break;
}
for(int i=1;i<=ans;i++)
{
if(i!=1)
printf(" ");
printf("%d",r[i]);
}
printf("\n");
}
return 0;
}
posted on 2011-05-09 22:59
lee1r 阅读(2388)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：搜索