华师一附中OI组

标题: 埃及分数 [打印本页]
作者: admin    时间: 2018-5-12 23:34
标题: 埃及分数
对于每一个非负有理数，我们知道它一定能划归成某些特殊真分数之和，特殊真分数要满足它们的分子为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    时间: 2018-5-12 23:35
对于此类搜索问题，搜索深度没有明显的上界，而且加数的选择在理论上也是无限的，也就是说宽度搜索连一层都扩展不完。

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

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

  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    时间: 2018-5-12 23:49
思路：

　　虽然是求最优解，但这道明显不是广搜吧（空间要求太高），而且很明显是用深搜做，即从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。



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2