东莞营销网站建设费用,wordpress相对地址,网站建设方案编写人,如何做推广呢#10022. 「一本通 1.3 练习 1」埃及分数 【题目描述】 在古埃及#xff0c;人们使用单位分数的和#xff08;形如 $\dfrac{1}{a}$ 的#xff0c;$a$ 是自然数#xff09;表示一切有理数。如#xff1a;$\dfrac{2}{3} \dfrac{1}{2} \dfrac{1}{6}$#xff0c…#10022. 「一本通 1.3 练习 1」埃及分数 【题目描述】 在古埃及人们使用单位分数的和形如 $\dfrac{1}{a}$ 的$a$ 是自然数表示一切有理数。如$\dfrac{2}{3} \dfrac{1}{2} \dfrac{1}{6}$但不允许 $\dfrac{2}{3} \dfrac{1}{3} \dfrac{1}{3}$因为加数中有相同的。对于一个分数 $\dfrac{a}{b}$表示方法有很多种但是哪种最好呢首先加数少的比加数多的好其次加数个数相同的最小的分数越大越好。 【算法】 $IDA^*$ 【代码】 #include bits/stdc.h
#define ll long long
using namespace std;
int a,b,dep;
ll ans[110],tmp[110];
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;
}
bool dfs(int now,ll y,ll aa,ll bb) {if(nowdep) {if(bb%aa) return 0;tmp[dep]bb/aa;if(!ans[dep]||tmp[dep]ans[dep]) memcpy(ans,tmp,sizeof(tmp));return 1;}int flag0;for(ll imax(bb/aa,y);;i) {if(bb*(dep-now1)aa*i) break;if(bbaa*i) continue;tmp[now]i;ll a2aa*i-bb; ll b2bb*i;ll ggcd(a2,b2);if(dfs(now1,i1,a2/g,b2/g)) flag1;}return flag;
}
int main() {scanf(%d%d,a,b);for(dep2;;dep) {if(dfs(1,b/a,a,b)) break;}for(int i1;idep;i) printf(%I64d ,ans[i]); puts();return 0;
}转载于:https://www.cnblogs.com/Willendless/p/9568505.html
