1288 埃及分数
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。 如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。 对于一个分数a/b,表示方法有很多种，但是哪种最好呢？ 首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越 好。 如： 19/45=1/3 + 1/12 + 1/180 19/45=1/3 + 1/15 + 1/45 19/45=1/3 + 1/18 + 1/30, 19/45=1/4 + 1/6 + 1/180 19/45=1/5 + 1/6 + 1/18. 最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。 给出a,b(0<a<b<1000),编程计算最好的表达方式。
输入描述 Input Description
a b
输出描述 Output Description
若干个数，自小到大排列，依次是单位分数的分母。
样例输入 Sample Input
19 45
样例输出 Sample Output
5 6 18
/* 经典基础IDA* 搜索无指定界限所以手动规定。因为要求分母尽量小，所以先找最小分母做下界 然后规定层数迭代搜 ans存分母 因为从小到大依次搜，层数加深，第一次找到的一定最优。 估价函数:若扩展到i层时,前i个分数之和为c/d,第i个分数为1/e 因为分母递增，所以接下来至少还需要>(a/b-c/d)/(1/e)个分数,总和才能到a/b. 此估价函数可以估计出最少多少步可以到达解,也就是说限定了层数。 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 10001 #define ll long long using namespace std; int minn; ll a,b,deep; ll ans[N],v[N]; inline ll read() { ll x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline ll gcd(ll x,ll y) { if(x<y) x^=y,y^=x,x^=y; int tmp; while(y){ tmp=x%y;x=y;y=tmp; }return x; } inline bool better(int d) { for(int i=d;i>=0;i--) return ans[i]==-1 || v[i]<ans[i]; return false; } inline int get(ll x,ll y)//当前下界 { for(int i=2;;++i) if(y<x*i) return i; } bool IDA(int d,int minn,ll aa,ll bb) { if(d==deep) { if(bb%aa) return false;//分子必须是1.因为已经约分，不必但心aa不为1 v[d]=bb/aa; if(better(d)) memcpy(ans,v,sizeof(ll)*(d+1)); return true; } bool flag=false; minn=std::max(minn,get(aa,bb));//也算剪枝，minn在不断增大 for(int i=minn;;++i) { if(bb*(deep-d+1)<=i*aa) break; //估价函数:因为i在增大,所以如果剩下的deep-d+1个分数全部都是1/i,加起来仍然不超过aa/bb，则无解,需要阔搜索层数 v[d]=i; ll b2=bb*i,a2=aa*i-bb;//计算aa/bb-1/i ll g=gcd(a2,b2); if(IDA(d+1,minn+1,a2/g,b2/g)) flag=true; } return flag; } int main() { a=read();b=read(); minn=get(a,b); for(deep=1;;deep++) { memset(ans,-1,sizeof ans);//don't forget if(IDA(0,get(a,b),a,b))//get 得到搜索下界 break; } for(int i=0;i<=deep;++i) printf("%d ",ans[i]); return 0; }