1288 埃及分数

题目描述 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*

我们可以限定搜索深度超出就返回

对于x/y 我们要确定一个k 使得 x/y<1/k 变式为 k>y/x 作为搜索上界

对于当前最大的 k 若有(depth-dep+1)*y<k*x 就直接返回

我们确定 k 为当前的上界如果后面的分母都选择 k

即还有(depth-dep+1) 层都用1/k 若比当前分数小不管后面怎么选都不会大于当前分数

直接退出就好了

Codevs 只要求最后一个数尽量小其他数没有要求

 1 #include <cstdio>
 2 #include <cctype>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define MAX 2147483647L
 6 
 7 using namespace std;
 8 
 9 typedef long long LL;
10 
11 const int MAXNDEPTH=15;
12 
13 LL a,b;
14 
15 LL ans[MAXNDEPTH],d[MAXNDEPTH];
16 
17 bool flag;
18 
19 inline void read(LL&x) {
20     int f=1;register char c=getchar();
21     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
22     for(;isdigit(c);x=x*10+c-48,c=getchar());
23     x=x*f;
24 }
25 
26 void DFS(LL x,LL y,LL k,LL dep) {
27     if(k==dep+1) return;
28     else if(y%x==0&&y/x>d[k-1]) {
29         d[k]=y/x;
30         if(!flag||d[k]<ans[k]) memcpy(ans,d,sizeof d);
31         flag=1;
32         return;
33     }
34     LL s=y/x;
35     if(s<=d[k-1]) s=d[k-1]+1;
36     if((dep-k+1)*y<x*s) return;//强力剪枝
37     LL t=(dep-k+1)*(y/x);
38     if(t>MAX) t=MAX-1;
39     if(flag&&t>=ans[dep]) t=ans[dep]-1;
40     for(LL i=s;i<=t;++i) {
41         d[k]=i;
42         LL m=__gcd(i*x-y,y*i);
43         DFS((i*x-y)/m,(y*i)/m,k+1,dep);
44     }
45 }
46 
47 int hh() {
48     read(a);read(b);
49     for(int i=1;i<=MAXNDEPTH;++i) {
50         DFS(a,b,1,i);
51         if(flag) {
52             for(int j=1;j<=i;++j) printf("%lld ",ans[j]);
53             printf("
");
54             break;
55         }
56     }
57     return 0;
58 }
59 
60 int sb=hh();
61 int main(int argc,char**argv) {;}

代码

若要求加数相同时，取最小的分数最大的，最小分数相同时，取次小分 数最大的

看以下代码

 1 #include <cstdio>
 2 #include <cctype>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define MAX 2147483647L
 6 
 7 using namespace std;
 8 
 9 typedef long long LL;
10 
11 const int MAXNDEPTH=15;
12 
13 LL a,b,dep;
14 
15 LL ans[MAXNDEPTH],d[MAXNDEPTH];
16 
17 bool flag;
18 
19 inline void read(LL&x) {
20     int f=1;register char c=getchar();
21     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
22     for(;isdigit(c);x=x*10+c-48,c=getchar());
23     x=x*f;
24 }
25 
26 inline bool judge(int depth) {
27     for(int i=depth;i;--i) 
28       if(d[i]!=ans[i]) return d[i]<ans[i];
29     return false;
30 }
31 
32 void DFS(LL x,LL y,LL now,LL depth) {
33     if(depth>dep) return;
34     if(x==1&&y>d[depth-1]) {
35         d[depth]=y;
36         if(!flag||judge(depth)) memcpy(ans,d,sizeof d);
37         flag=1;
38         return;
39     }
40     if(now<y/x+1) now=y/x+1;
41     if(now<=d[depth-1]) now=d[depth-1]+1;
42     for(LL i=now;;++i) {
43         if((dep-depth+1)*y<x*i) return;
44         d[depth]=i;
45         LL m=__gcd(i*x-y,y*i);
46         DFS((i*x-y)/m,(y*i)/m,i+1,depth+1);
47     }
48 }
49 
50 int hh() {
51     freopen("egypt.in","r",stdin);
52     freopen("egypt.out","w",stdout);
53     read(a);read(b);
54     for(dep=2;dep<=MAXNDEPTH;++dep) {
55         DFS(a,b,b/a+1,1);
56         if(flag) {
57             for(int j=1;j<=dep;++j) printf("%I64d ",ans[j]);
58             printf("
");
59             break;
60         }
61     }
62     return 0;
63 }
64 
65 int sb=hh();
66 int main(int argc,char**argv) {;}

代码