验证古埃及分数猜想

说在前面

有一个著名的分马问题：老财主临终前把三个儿子叫到身边说，家里有17匹马可当遗产分，大儿子分得1/2，二儿子分得1/3，三儿子分得1/9。不许杀马，不许流血，必须按老父亲的遗嘱分配马匹。

三个儿子百思不得其解，于是请来村里的智伯帮助解决难题。智伯想了又想，终于找出了答案。

智伯是怎么解决这个难题的呢？

他从自己家里牵来了一匹马，凑成18匹。大儿子得1/2是9匹，二儿子分1/3是6匹，三儿子分1/9是2匹。9+6+2等于17匹，还剩下一匹，是智伯从自家牵来的，牵回去就可以了。

算法原理

分马问题中有17/18 = 1/2 + 1/3 + 1/9。

其中的诀窍是把有理数17/18分解成了3个分子为1的分数，且其分母均为18的因数。古代埃及人在进行分数运算时，只使用分子是1的分数。因此这种分数也叫做埃及分数，或者叫单分子分数。

古埃及分数猜想：将大于1的整数任意分成有限个子集，必然有一个子集中的部分整数倒数加起来为1。

例如只要有一个子集中有2、3、6，就有1 = 1/2 + 1/3 + 1/6。

对于任意有理数，我们都可以用简单的算法找到古埃及分数表示。

现在请你编写一个自定义函数，将任意一个有理数展开成古埃及分数的表示形式。函数头说明如下：

函数功能：使用古埃及分数表示任意有理数函数名：egyptian_fraction(nr, dr)参数表：nr -- 分子（numerator）； dr -- 分母（denominator）。返回值：返回存储了古埃及分数中分母序列的列表。例1，当nr=17,dr=18时，返回[2, 3, 9]。例2，当nr=11,dr=12时，返回[2, 3, 12]。代码实现

#!/usr/bin/python3# 文件名:验证古埃及分数猜想# 作者：巧若拙@Python算法之旅# 时间：2022-3-16"""函数功能：使用古埃及分数表示任意有理数函数名：egyptian_fraction(nr, dr)参数表：nr -- 分子（numerator）；dr -- 分母（denominator）。返回值：返回存储了古埃及分数中分母序列的列表。例1，当nr=17,dr=18时，返回[2, 3, 9]。例2，当nr=11,dr=12时，返回[2, 3, 12]。"""def egyptian_fraction(nr, dr):import mathans = [] #用来存储古埃及分数中分母序列的列表while nr != 0:x = math.ceil(dr / nr)ans.append(x)nr = x * nr - drdr = dr * xreturn ans#主函数nr, dr = 17, 18#nr, dr = 11, 12nr, dr = 9, 10ans = egyptian_fraction(nr, dr)print(ans)print(f"{nr}/{dr} = ", end="")for d in ans[:-1]:print(f"1/{d} + ", end="")print(f"1/{ans[-1]}")

课后练习

篇头的分马问题总共马匹数为17，三个儿子所占比例分别为1/2，1/3和1/9，我们可以分别用变量表示为a=17，b=2，c=3，d=9。除了这一组取值，还有a=11，b=2，c=3，d=12组合，即11/12 = 1/2 + 1/3 + 1/12。

除此之外，你还知道哪些数据组合可以代入到分马问题中吗？请编程实现之。

需要本文PPT、源代码和课后练习答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注Python算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类

关键词： 函数功能 就可以了 学习方式