题目链接：点击打开链接
题目描述：
在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。对于一个分数a/b,表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
如：19/45=1/3 + 1/12 + 1/18019/45=1/3 + 1/15 + 1/4519/45=1/3 + 1/18 + 1/30,19/45=1/4 + 1/6 + 1/18019/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输出：若干个数，自小到大排列，依次是单位分数的分母。
解题思路：迭代加深搜索，从1开始枚举深度即可
注意思想：精度问题，通过约分来控制即可gcd，同时防止溢出long long
代码：
#include <cstdio>#include <cstring>#include <iostream>#define MAXN 10000typedef long long LL;using namespace std;int maxd;LL ans[MAXN];LL v[MAXN];LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}int get_first(int a,int b){if(b%a==0) return b/a;else return (b/a+1);}bool better(int d){// for(int i=d;i>=0;–i)if(v[i]!=ans[i]){//return ans[i]==-1||v[i]<ans[i];// }return ans[d]==-1||v[d]<ans[d];// return false;}bool dfs(int d,int from,LL aa,LL bb){if(d==maxd){if(bb%aa) return false;v[d]=bb/aa;if(better(d)) memcpy(ans,v,sizeof(LL)*(d+1));///赋值时注意LL类型return true;}bool ok=false;from=max(from,get_first(aa,bb));for(int i=from;;i++){if(bb*(maxd+1-d)<=i*aa) break;///防止溢出v[d]=i;LL b2=bb*i;LL a2=aa*i-bb;LL g=gcd(a2,b2);if(dfs(d+1,i+1,a2/g,b2/g)) ok=true;}return ok;}int main(){int a,b;while(scanf("%d%d",&a,&b)==2){for(maxd=1;;maxd++){///IDmemset(ans,-1,sizeof(ans));if(dfs(1,get_first(a,b),a,b)) break;}for(int i=1;ans[i]!=-1;i++)// if(ans[i]>0)printf("%lld ",ans[i]);printf("\n");}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，偶尔会想，如果人生真如一场电子游戏，
