Python使用贪心算法分解古埃及分数

==============

版权声明：由于公众号后台规则问题，本文暂时无法设置原创标记，但仍属原创内容，微信公众号“Python小屋”坚持只发原创技术文章。

=============

问题描述：

传说古埃及人只使用整数和分子为1的真分数，需要表示其他分数时就使用整数和若干分子为1的分数之和。同一个真分数有多种等价的表示形式，要求得到的分数最少，也就是每个分数的分母尽可能小。

假设分数为a/b，其中a<b且a和b的最大公约数为1，则有

b=a*c+d

其中c=b//a和d=b%a<a。上式两边同时除以a，得

b/a = c+d/a < c+1

记e=c+1，然后对上式求倒数，得

a/b>1/e

可知1/e是小于a/b的最大分数，a/b - 1/e后的剩余部分为

a/b - 1/e = (a*e-b)/(b*e)

对剩余部分继续分解，重复这个过程，直到等于1为止。

函数main()接收两个自然数a和b作为参数，分别表示分数a/b的分子和分母，首先对分数a/b进行约分，然后按照上面描述的算法进行分解，分解过程中进行必要的约分。最终返回分解结果字符串。

参考代码：

运行结果：