题干

古埃及人只用分子为1的分数，在表示一个真分数时，将其分解为若干个埃及分数之和。例如，7/8表示为 1/2+1/3+1/24。要求把一个真分数表示为最少的埃及分数之和的形式。更加详细的描述请自行百度。

思路

要求表示为最少的埃及分数之和的形式，那就要求我们分解出来得到埃及分数的分母尽可能的小。
按照贪心的策略，我们可以在每一次分解时都取出最大的那个埃及分数，也就是分母最小的埃及分数。然后将所给的真分数分解为一个更小的真分数+埃及分数的形式，然后对该真分数继续分解，直到把真分数都表示成埃及分数的形式。
那么，现在的问题就转成了怎么求出每次的最大的埃及分数了。下面就行相应分析：

假设一个真分数为\(\frac{a}{b}\)，那么就有\(b>a\),那么，\(b\)就可以表示成以下形式：

\[\begin{eqnarray*} &&b=a*k+c \\ &&\Rightarrow \frac{b}{a}=k+\frac{c}{a} \\ &&\Rightarrow \frac{a}{b}=\frac{1}{k+ \frac{c}{a} },\frac{c}{a}<1\\ &&\Rightarrow \frac{a}{b}=\frac{1}{k+ \frac{c}{a} }>\frac{1}{k+ 1 } \end{eqnarray*} \]

那么，\(\frac{a}{b}\)的最大埃及分数为\(\frac{1}{k+1}\),那么，问题应该就可以解决了。

代码

/* 埃及分数 */
#include 
#include 
using namespace std;
void eg_score(int a, int b) {
    cout << "a/b =";
    while (a > 1) {
        int k = b / a + 1;
        cout << "1/" << k << "+";  
        a = a * k - b;   //求拆解后的分子和分母
        b = b * k;
        int r = __gcd(a, b);  //这里是求a,b的最大公约数
        if (r > 1) {          //将拆解过后的分数化为真分数
            a = a / r;
            b = b / r;
        }
    }
    cout << "1/" << b;
}

int main() {
    int a, b;
    cin >> a >> b;
    eg_score(a, b);
    return 0;
}

总结

课本上把这道题的算法归类到贪心应该就是在求最大的埃及分数那一步体现出来的。你要求最少的埃及分数，那就是要求每次分解出来的埃及分数尽可能地大，这样就减少了分解出来的埃及分数的个数。