問(wèn)題描述：在古埃及，人們使用單位分?jǐn)?shù)的和（即1/a，a是自然數(shù)）表示一切有理數(shù)。例如，2/3=1/2+1/6，但不允許2/3=1/3+1/3，因?yàn)榧訑?shù)中不允許有相同的，則最小的分?jǐn)?shù)越大越好。例如19/45=1/5+1/6+1/18是最優(yōu)方案。

分析：題目看似不難，但是有陷阱，沒(méi)有給出深度，一味回溯，肯定出不來(lái)，作者給出的思路就是用迭代法，加剪枝。每次枚舉深度上限，每次都判斷是否比之前的解更小，每次搜索時(shí)候判斷當(dāng)前的數(shù)x剩下的深度是不是小于剩下的部分，如果小于直接退出，因?yàn)橄旅娴拿杜e分?jǐn)?shù)只會(huì)越來(lái)越小。

看看里面用到的數(shù)學(xué)知識(shí)，實(shí)現(xiàn)求一個(gè)分?jǐn)?shù)的分解的第一項(xiàng)，要使它最大（然后從從這個(gè)最小分母開(kāi)始遍歷，相當(dāng)于起點(diǎn)）。例如495/499=1/2+1/5+1/6+1/8+1/3992+1/14970，要求起點(diǎn)，也就是1/2，同時(shí)正好滿(mǎn)足最終解，這里面相當(dāng)于簡(jiǎn)單除法，，要使c最大，也就是1/c最小，，。

歐幾里得算法，也叫輾轉(zhuǎn)相除法，是數(shù)論里面廣為人知的算法，作用是求最大公約數(shù)。

定理：兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的那個(gè)數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。

舉例說(shuō)明：

18 和10的最大公約數(shù)

18=1*10+8

10=1*8+2

8=2*4+0

所以最大公約數(shù)為2

證明：

第一種：

設(shè)a=kb+r，r=a-kb

設(shè)a,b的最大公約數(shù)為n，r/n=a/n-kb/n

因?yàn)閍/n和kb/n都能整除，所以r也可以被n整除，所以a,b和r的最大公約數(shù)是n。

第二種：

設(shè)a,b的最大公約數(shù)為x，a=mx，b=nx

r=mx-knx=(m-kn)x，所以r是可以被x整除。

所以r和a,b的最大公約數(shù)是x

程序?qū)崿F(xiàn)：

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a%b); }

主體實(shí)現(xiàn)：

#include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<iostream> using namespace std; const int maxn = 100 + 5; typedef long long LL; int maxd; LL v[maxn],ans[maxn]; int get_first(LL a,LL b) {return b / a + 1;//取分子為1的最大組成分?jǐn)?shù) } LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a%b); } bool better(int d) {for (int i = d; i >= 0; i--)if (v[i] != ans[i]) {return ans[i] == -1 || v[i]<ans[i];//分母越大分?jǐn)?shù)越小,最小的分?jǐn)?shù)越大越好}return false; } bool dfs(int d, int from, LL a, LL b) {if (d == maxd) {if (b%a)return false;//如果不能整除就返回v[d] = b / a;if (better(d))memcpy(ans, v, sizeof(LL)*(d + 1));return true;}from = max(from, get_first(a, b));bool ok = false;for (int i = from;; i++) {//從from開(kāi)始分母依次增大if (b*(maxd - d + 1) <= i * a)break;//剪枝，這里也是分母太大，分?jǐn)?shù)很小的時(shí)候，無(wú)窮循環(huán)結(jié)束的時(shí)候v[d] = i;//計(jì)算剩余部分LL bb = b * i;LL aa = a * i - b;LL g = gcd(aa, bb);//最大公約數(shù)if (dfs(d + 1, i + 1, aa / g, bb / g))ok = true;//回溯}return ok; } int main() {int a=0, b=0,kase=0;while (cin >> a >> b) {int ok = 0;for (maxd = 1; maxd <= 100; maxd++) {memset(ans, -1, sizeof(ans));if (dfs(0, get_first(a, b), a, b)) { ok = 1; break; }}cout << "Case " << ++kase << ": ";if (ok) {cout << a << "/" << b << "=";for (int i = 0; i < maxd; i++) cout << "1/" << ans[i] << "+";cout << "1/" << ans[maxd] << "\n";}else cout << "No solution.\n";}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的埃及分数问题——迭代加深搜索的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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