Description：
在古埃及，人們使用單位分數(shù)的和(形如1/a的, a是自然數(shù))表示一切有理數(shù)。如：2/3=1/2+1/6,但不允許2/3=1/3+1/3,因為加數(shù)中有相同的。對于一個分數(shù)a/b,表示方法有很多種，但是哪種最好呢？首先，加數(shù)少的比加數(shù)多的好，其次，加數(shù)個數(shù)相同的，最小的分數(shù)越大越好。
如：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深搜（因為分數(shù)的個數(shù)不限），也不能用BFS廣搜（因為分母也是無限的），但由題意可知，我們要做到的是最少的分數(shù)個數(shù)，并且最大的分母盡量小，我們可以考慮一種新的搜索——迭代加深。可以認為它結(jié)合了DFS與BFS，在限定的層數(shù)內(nèi)深搜
　
　于是這道題我們便找到了正確的搜索方法：先不斷遞增分數(shù)的個數(shù)，第一次找到的一定是個數(shù)最小的解，然后處理最優(yōu)性問題，首先我們不能在找到一組解之后就直接return ，這樣只滿足了第一個目標(biāo)，正確做法應(yīng)該是返回上一層繼續(xù)遞歸。那么什么情況下才會break呢？我們假設(shè)當(dāng)前還可以枚舉 d 個分數(shù) ， 當(dāng)前剩余的分數(shù)是 a/b , 枚舉的分母為 i ， 如果d/i<=a/b,我們就可以 break 掉了，這是因為如果后面都是 1/i 也只能小于等于目標(biāo)，那么肯定不存在解了，因為分母必須嚴格遞增。

#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); //尋找當(dāng)前層數(shù)分母的最小值l2 = min(y * (limt -dep + 1) / x , best - 1);//尋找當(dāng)前層數(shù)分母的最大值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++; // 枚舉當(dāng)前深搜的層數(shù) dfs(a,b,1);}for(LL i = 1; i < limt ; i ++) cout <<"1/"<<ans[i]<<" + ";cout<<"1/"<<ans[limt]; }

總結(jié)

以上是生活随笔為你收集整理的埃及分数 （迭代加深入门）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。