埃及分数 （迭代加深入门）

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),编程计算最好的表达方式。
输入：a b
输出：一个等式

Sample Input：
3 4
Sample Output:
3/4 = 1/2 + 1/4

题解：
　这道题显然我们既不能用DFS深搜（因为分数的个数不限），也不能用BFS广搜（因为分母也是无限的），但由题意可知，我们要做到的是最少的分数个数，并且最大的分母尽量小，我们可以考虑一种新的搜索——迭代加深。可以认为它结合了DFS与BFS，在限定的层数内深搜
　
　于是这道题我们便找到了正确的搜索方法：先不断递增分数的个数，第一次找到的一定是个数最小的解，然后处理最优性问题，首先我们不能在找到一组解之后就直接return ，这样只满足了第一个目标，正确做法应该是返回上一层继续递归。那么什么情况下才会break呢？我们假设当前还可以枚举 d 个分数 ， 当前剩余的分数是 a/b , 枚举的分母为 i ， 如果d/i<=a/b,我们就可以 break 掉了，这是因为如果后面都是 1/i 也只能小于等于目标，那么肯定不存在解了，因为分母必须严格递增。

#include <bits/stdc++.h> #define N 100001 #define min(x,y) x > y ? y : x #define max(x,y) x > y ? x : y using namespace std; typedef long long LL; LL a,b,best,ans[N],flag,limt,way[N];void dfs(LL x , LL y , LL dep) {LL l1,l2,xx,yy,i,j;l1 = max(way[dep - 1] + 1 , y / x); //寻找当前层数分母的最小值l2 = min(y * (limt -dep + 1) / x , best - 1);//寻找当前层数分母的最大值for(i = l1 ; i <= l2 ; i ++){xx = x; yy = y; way[dep] = i; //xx = xx * i - yy; //计算剩余的分子if(x < 0) continue;yy = yy * i; //计算剩余的分母if(dep < limt) dfs(xx,yy,dep + 1);if(i < best && xx == 0){flag = 1 ; best = i;for(j = 1 ; j <= limt ; j ++)ans[j] = way[j]; //更新答案}} } int main() {//freopen("lx.in","r",stdin);cin >> a >> b;cout<<a<<"/"<<b<<" = ";flag = 0 ; way[0] = 1 ; best = 99999999;while(flag == 0){limt++; // 枚举当前深搜的层数 dfs(a,b,1);}for(LL i = 1; i < limt ; i ++) cout <<"1/"<<ans[i]<<" + ";cout<<"1/"<<ans[limt]; }

总结

以上是生活随笔为你收集整理的埃及分数 （迭代加深入门）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。