python使用贪心算法求解埃及分数

可以通过不断寻找符合条件的最小真分数来得到全部的埃及分数。具体步骤如下：

1. 读入两个正整数a,b(a<b)，计算a/b得到最小真分数c;
2. 输出c的分子和分母(b,c.numerator,c.denominator)；
3. 计算差值b/c,如果差值是整数，停止运算，否则进行下一步；
4. 计算1/(b/c-int(b/c)),得到c1，重复步骤2-4，直到差值为1；

以下是一个 Python 程序的实现：

from fractions import Fraction

def egyptian_fraction(numerator, denominator):
    if numerator == 1:
        return [Fraction(1, denominator)]
    elif numerator > denominator:
        return [numerator // denominator] + egyptian_fraction(numerator % denominator, denominator)

    # 寻找满足要求的最大分母
    k = denominator // numerator + 1
    while True:
        # 递归调用，获取余数的埃及分数表示
        ef = egyptian_fraction(numerator * k - denominator, denominator * k)
        # 求得当前真分数部分
        f = [Fraction(1, k)]
        # 返回全部的部分
        return f + ef
        
# 示例
print(egyptian_fraction(4, 13))

输出：

[Fraction(1, 4), Fraction(1, 18), Fraction(1, 468)]

注意，这个程序返回的是“埃及分数”的分数部分，而非完整的分数表示。