首页 > > 程序设计 > C/C++ >

埃及分数问题_迭代加深搜索_C++

2018-06-17 23:55:33来源：未知阅读 ()

一、题目背景

　　http://codevs.cn/problem/1288/

　　给出一个真分数，求用最少的1/a形式的分数表示出这个真分数，在数量相同的情况下保证最小的分数最大，且每个分数不同。

　　如 19/45=1/3 + 1/12 + 1/180

二、迭代加深搜索

　　迭代加深搜索可以看做带深度限制的DFS。

　　首先设置一个搜索深度，然后进行DFS，当目前深度达到限制深度后验证当前方案的合理性，更新答案。

　　不断调整搜索深度，直到找到最优解。

三、埃及分数具体实现

　　我们用dep限制搜索层数，先从2开始，每次深度+1

　　搜索时每一层比上一层的分数小，即分母一次比一次大

　　每次枚举出 1/a 后，用当前分数减去，然后递归传递剩余的分数

　　每层搜索枚举的限制条件：

　　　　1、保证当前深度分母大于上一深度分母

　　　　2、枚举的1/a小于当前分数，不可能存在等于的状态，因为此种最优解会在限制深度较小的时候出现

　　　　3、设当前剩余分数为x/y，剩余深度为d，则 x/y<d/a → a<d/x*y。

　　　　　不妨先设之后枚举的分母都为 a，那么最后也就刚好达到 x/y ，但又因分数不能相等，所以 a 必须小于该值，即把分数调大。如果分数很小，那么就永远够不着目标分数

　　当深度达到限制深度时，只需判断剩余的分数是否满足1/a的形式，然后更新结果

　　记得开long long ，使用%lld输出，因为通分的时候数据会很大

　　时间复杂度和搜索大致一致，因为当前限制深度的时间复杂度远大于上一次限制深度的时间复杂度，所以之前深度的时间可以忽略

　　优点是空间开支特别小

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 #define N 1000
 8 using namespace std;
 9 
10 long long ans[N],s[N],mo,ch;
11 int dep;
12 long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}
13 void outp()
14 {
15     int i;
16     if (ans[dep]>s[dep])
17         {
18             for (i=1;i<=dep;i++)
19             {
20                 ans[i]=s[i];
21             }
22         } 
23 }
24 void dfs(long long x,long long y,int d)
25 {
26     long long a,b,i,w;
27     if (d==dep)
28     {
29         s[d]=y;
30         if ((x==1)&&(s[d]>s[d-1])) outp();
31         return;
32     }
33     for (i=max(s[d-1]+1,y/x+1);i<(dep-d+1)*y/x;i++)
34     {
35         b=y*i/gcd(y,i);
36         a=b/y*x-b/i;
37         w=gcd(a,b);
38         a/=w;
39         b/=w;
40         s[d]=i;
41         dfs(a,b,d+1);
42     }
43 }
44 int main()
45 {
46     int i=0,j;
47     scanf("%lld%lld",&ch,&mo);
48     i=gcd(ch,mo);
49     ch/=i;
50     mo/=i;
51     for (dep=2;;dep++)
52     {
53         ans[1]=0;
54         s[0]=0;
55         ans[dep]=2000000000;
56         dfs(ch,mo,1);
57         if (ans[1]!=0) break;
58     }
60     for (j=1;j<=dep;j++)
61     {
62         printf("%lld ",ans[j]);
63     }
64     printf("\n");
65     return 0;
66 }