一、題目背景
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("%d%d",&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 }
版權所有，轉載請聯系作者，違者必究
QQ：740929894
