题目
题目描述
在古埃及，人们使用单位分数的和（形如1/a的，a是自然数）表示一切有理数。如：2/3=1/2+1/6，但不允许2/3=1/3+1/3，因为加数中有相同的。对于一个分数a/b，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数值越大越好。
如：
|
1 2 3 4 5 6 |
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），编程计算最好的表达方式。
输入
只有一行，为a,b。（0<a<b<1000）
输出
若干个数，自小到大排列，依次是单位分数的分母，每个数字以空格隔开。
样例输入
|
1 2 |
19 45 |
样例输出
|
1 2 |
5 6 18 |
题解
埃及分数真的是一个神奇的东西，网上很多题解直接就将IDA*算法，但是为什么拿到这道题就会想到IDA*呢？
我们可以发现，本题的特别之处在于它的状态空间是无限大的。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<cmath> #define MAXN 5100 typedef long long ll; using namespace std; ll a,b; ll dep=0; ll ans[MAXN],v[MAXN]; inline ll gcd(ll x,ll y){ return y==0? x : gcd(y,x%y); } inline ll G_first(ll xx,ll yy) {//满足1/c<=xx/yy的最小c return yy/xx+1; } inline bool better() { for(int i=dep;i>=1;i--) if(ans[i]!=v[i]) return ans[i]==0||v[i]<ans[i]; return false; } inline bool dfs(ll now,ll from,ll xx,ll yy){ if(now==dep) { if(yy%xx) return false;//保证最后一个的xx为1（约分后 v[now]=yy/xx; if(better()) for(ll i=1;i<=dep;i++) ans[i]=v[i]; return true; } bool ok=false; from=max(from,G_first(xx,yy)); for(ll i=from; ;i++){ // (dep-now+1)/i <= xx/yy 移项得 if(yy*(dep-now+1)<=i*xx) break;//如果剩下的分数全是1/i加起来也无法超过xx/yy ,则剪去 v[now]=i; ll y2=yy*i,x2=xx*i-yy; ll g=gcd(x2,y2); if(dfs(now+1,i+1,x2/g,y2/g)) ok=true; } return ok; } int main(){ scanf("%lld%lld",&a,&b); else { bool ok=false; for(dep=1;;dep++){ memset(ans,0,sizeof(ans)); if(dfs(1,G_first(a,b),a,b)){ ok=true; break; } } if(ok) for(int i=1;i<=dep;i++) printf("%d ",ans[i]); } return 0; } |