埃及分数

admin

对于每一个非负有理数，我们知道它一定能划归成某些特殊真分数之和，特殊真分数要满足它们的分子为1，但是我们知道，对于无穷级数1/2+1/3+1/4…。虽然，它是发散的，但是改级数增长得极为缓慢，例如到了数百万之后，和也在18~19左右。

         若干年来，不断有人宣称发现了该级数的特殊性质，这些都对这个问题的研究起到了深远的影响。

         你的任务来了，要求给你个真分数，你需要将其化简为最少的若干特殊真分数之和，你要输出这个序列（序列按递增序）。

         如果有不同的方案，则分数个数相同的情况下使最大的分母最小。若还相同，则使次大的分母最大……以此类推。

         如：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

最好的是最后一种，因为18 比180, 45, 30,都小。

admin

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<cstring>
   
4. #include<algorithm>
   
5. using namespace std;
   
6. const int MAXN=20000;
   
7. long long maxd;
   
8. long long v[MAXN],ans[MAXN];///v是暂时存放的满足题意的分母的数组，ans是记录满足题意的最优分母值的数组。
   
9. long long gcd(long long a,long long b)///求最大公约数
   
10. {
    
11.     long long m;
    
12.     while(a!=0)
    
13.     {
    
14.        m=b%a;
    
15.        b=a;
    
16.        a=m;
    
17.     }
    
18.     return b;
    
19. }
    
20. long long getfirst(long long a,long long b)///取比a/b小的最大分数，分子必须为1
    
21. {
    
22.     long long i,j;
    
23.     for(i=2;;i++)
    
24.     {
    
25.         if(b<a*i)
    
26.         {
    
27.                 break;
    
28.         }
    
29.     }
    
30.     return i;
    
31. }
    
32. bool better(long long d)///必要的判断，这组分数之和是否满足最优解
    
33. {
    
34.     long long i;
    
35.     bool flag=true;
    
36.     if(ans[d]==-1)///由于初始化ans是-1，如果是第一次出现的满足题意的解，返回true
    
37.         return true;
    
38.     for(i=d;i>=0;i--)
    
39.     {
    
40.         if(v[i]==ans[i])///从高位进行判断大小，题意要求
    
41.             continue;
    
42.         else if(v[i]>ans[i])
    
43.         {
    
44.                //return false;
    
45.                flag=false;
    
46.                break;
    
47.         }
    
48.         else
    
49.         {
    
50.                 break;
    
51.         }
    
52.     }
    
53.     return flag;
    
54. }
    
55. bool dfs(long long a,long long b,long long from,long long d)//深度为d
    
56. {
    
57.     long long aa,bb,g,i;
    
58.     bool ok;
    
59.    // cout<<from<<endl;
    
60.     if(d==maxd)
    
61.     {
    
62.         if(a!=1)
    
63.             return false;
    
64.         for(i=0;i<=d-1;i++)
    
65.         {
    
66.             if(v[i]==b)
    
67.             {
    
68.                 return false;
    
69.             }
    
70. 
    
71.         }
    
72.         v[d]=b;
    
73.         sort(v,v+d);
    
74.         if(better(d))
    
75.             memcpy(ans,v,sizeof(long long)*(d+1));
    
76.         return true;
    
77.     }
    
78.     ok=false;
    
79.     //重要！！！
    
80.     from=max(from,getfirst(a,b));///枚举起点，去上一次加一的分母值和比a/b小的最大分数的分母中更大的。
    
81.     for(i=from;;i++)
    
82.     {
    
83.         ///剪枝，如果c/d（前i个分数之和）+1/e*（maxd-i）<a/b，可以直接break;
    
84.         if(b*(maxd+1-d)<=a*i)
    
85.             break;
    
86.         v[d]=i;
    
87.         aa=a*i-b;
    
88.         bb=b*i;
    
89.         g=gcd(aa,bb);
    
90.         aa=aa/g;
    
91.         bb=bb/g;///约分
    
92.         if(dfs(aa,bb,i+1,d+1))
    
93.             ok=true;
    
94.     }
    
95.     return ok;
    
96. }
    
97. int main()
    
98. {
    
99.     long long a,b,aa,bb,i,g;
    
100.     while(cin>>a>>b)
     
101.     {
     
102.         if(a==0)
     
103.         {
     
104.             cout<<a<<"/"<<b<<"=0"<<endl;
     
105.             continue;
     
106.         }
     
107.         memset(ans,-1,sizeof(ans));
     
108.         g=gcd(a,b);
     
109.         aa=a/g;
     
110.         bb=b/g;
     
111.         if(aa==1)
     
112.         {
     
113.             printf("%d/%d=%d/%d\n",a,b,aa,bb);
     
114.         }
     
115.         else
     
116.         {
     
117.             for(maxd=1;;maxd++)
     
118.             {
     
119.                 if(dfs(aa,bb,getfirst(aa,bb),0))
     
120.                     break;
     
121.             }
     
122.             cout<<a<<"/"<<b<<"=";
     
123.             for(i=0;i<=maxd-1;i++)
     
124.                 cout<<"1/"<<ans[i]<<"+";
     
125.             cout<<"1/"<<ans[i];
     
126.             cout<<endl;
     
127.         }
     
128.     }
     
129.     return 0;
     
130. }
     

复制代码

admin

思路：

　　虽然是求最优解，但这道明显不是广搜吧（空间要求太高），而且很明显是用深搜做，即从1~无穷，每一个分母，都有选中和不选中两种状态，如果选中，那么就减去这个分数，没有就是跳过，但无穷到底是哪里呢，而且具体要选几个呢，这就是这道题的难点。因为多组答案的优先级是由单位分数的个数首先决定，那么我们可以逐次放宽个数的限制，即迭代加深搜索。

　　迭代加深搜索的具体内容：第一次，我限制只能用k个单位分数来完成，如果找完所有情况，还是没找到解，那么我现在用k+1个单位分数解决，这样优点如下：

　　1. 肯定保证最优解，因为我用k个来完成分解就说明比k小的个数分解不出来，如果分解得出来，我在那时就退出循环了。

　　2. 虽然看似重复进行了很多遍的搜索，但上一层的搜索量和下一层比起来太少了，不影响总的时间复杂度。

抛开逐步解开个数限制外，每一个个数限制下的做法和平常的深入优先搜索大致相同，要注意剪枝！

主要的两个剪枝如下：

　　1. 限制开头：并不是每次都要从1开始遍历分母，假设现在要分解a/b，那么分母b/a就是起点，因为b/a的分数太大，起始点已经超过了a/b，没有什么意义：1/(b/a)=a/b ，假设起点s<b/a，那么显而易见，起点的分数已经比我们要的总和（a/b）大了。

　　2. 限制结尾：

　　　　（1）比较简单的限制结尾可以这样看：如果我已经找到分母k了，而现在要分解得分数是a/b，现在还要找m个单位分数，那么可以想象：有可能 m * ( 1/k ) 还小于a/b，也就是说就算全是1/k，我凑够m个，也达不到a/b，那么说明前面的分配方案肯定有无，直接可以return了。加上这个剪枝已经可以得到答案了，只是时间有点慢罢了。

　　　　（2）现在我们假设终点为t，还要找m个单位分数，现在的分数剩下a/b，那么很容易有m * (1/t) <= a / b  ，也就是说我如果m个都用最小的，肯定小于等于a/b。（等于号就是说有可能m=1，我可能直接终点就是答案，如果m>1，那么终点肯定也不可能选到，假设选了（后面还要选（m-1）个，肯定凑不够）这样子，由上面的式子，经过变换，可以得到 t >= m*b/a ，也就是说终点为m*b/a。

admin

对于此类搜索问题，搜索深度没有明显的上界，而且加数的选择在理论上也是无限的，也就是说宽度搜索连一层都扩展不完。

利用迭代加深搜索（IDA*）可以解决上面的问题。一方面我们要解决，利用BFS从小到大枚举深度上限maxd，虽然理论上深度是无限的，但是只要保证有解，深度值必然在有限的时间内能枚举到。

另一方面，我们还要解决每次枚举的值无限的问题，可以借助maxd来“剪枝”，以此题为例，每一次枚举的的分母个数必然有一个结束值，否则就会出现无限下去的尴尬了。那么当扩展到第i层时，第i层分数值为1/e，那么接下来由于分母是以递增顺序进行的，那么分数值都不会大于1/e，如果c/d（前i个分数之和）+1/e*（maxd-i）<a/b，可以直接break;因为起码深度不够，要再加深度。