[CODEVS1225]埃及分数解题报告

本文主要是介绍[CODEVS1225]埃及分数解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

据说这是DFS-ID的一道入门水题。。但是我还是看了题解以后才做出来。

主要思路：①迭代加深确定深度；（分数个数最小）②在存在可行解的深度上求最优解。（最小分母最大）

注意问题：

①精度问题，不能用小数来做，应该保存一个分母和分子，并注意时刻约分。

②大小问题，可能会爆int！

③数据问题！明明可能会有多个最小分母最大的解，但数据是。。按照搜索的顺序的第一个。。

#include<iostream>
#include<cmath>
using namespace std;
#include<cstdio>
#include<cstring>
#include<cstdlib>
typedef long long lld;
int m=1;
lld ans[2000],now[2000];
bool flag;
lld gcd(lld a,lld b){if(!b)return a;else return gcd(b,a%b);
}
void yuefen(lld &a,lld &b){lld g=gcd(a,b);a/=g,b/=g;
}
void dfs(int x,int pred,lld A,lld B){lld a=A,b=B;yuefen(a,b);if(x==1){if(a==1&&b>pred){if(flag&&b>=ans[1])return;int i=0;/*printf("%d\n",b);if(flag&&b==ans[1])for(i=2;i<=m;++i)if(now[i]<ans[i])break;else if(now[i]>ans[i])return;if(i>m)return;*/now[1]=b;flag=1;memcpy(ans,now,(m+1)<<3);return;}return;}for(int i=pred,maxi=ceil((double)b*x/a);i<=maxi;++i){now[x]=i;dfs(x-1,i,a*i-b,b*i);}
}
int main(){lld a,b;cin>>a>>b;yuefen(a,b);while(!flag){dfs(m,1,a,b);++m;}for(int i=m;--i;)printf("%d ",ans[i]);
}

这篇关于[CODEVS1225]埃及分数解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---