給出一個分數(shù)，比如19/45，把它寫成若干個形如1/Ri的分數(shù)的和的形式，比如19/45=1/5+1/6+1/18，要求分母不能重復(fù)使用并且使用的分數(shù)的個數(shù)最少。（如果有多組個數(shù)相同的解，最后的分數(shù)的分母越小越好，這對于題目來說是次要的。）
1、分母從小到大搜索
為了避免重復(fù)搜索
2、使用迭代加深搜索
求“步驟數(shù)最少”這類問題，基本上有兩種似乎：廣搜、迭代加深搜索。對于這道題來說，如果廣搜將永遠得不到結(jié)果，分母可以無限大！但是迭代加深搜索就比較好，雖然做了許多重復(fù)工作，但狀態(tài)空間至少被限制住了。如果當前正在枚舉的分母，使得接下來的選擇即使每次都選擇最大，達到最大深度的時候也不可能達到目標分數(shù)，那么當前正在枚舉的分母及比它還大的分母，都不需要枚舉了。這樣可以給分母確定一個上界。另外，已經(jīng)得到的結(jié)果加上當前枚舉的分母對應(yīng)的分數(shù)，要小于等于目標分數(shù)，這樣給分母確定了一個下界（可以在O(1)的復(fù)雜度內(nèi)確定這個下界）。
在下面的代碼中，因為確定上下界都使用了浮點運算，最終還是需要把當前結(jié)果和目標結(jié)果比較。
浮點運算～真讓人糾結(jié)的東西！
以下是我的代碼：
#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 閱讀(2430)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：搜索