JAVA算法:埃及分数(Egyptian Fraction)
问题描述:
埃及分数是指分子是1的分数,也叫单位分数。古代埃及人在进行分数运算时。只使用分子是1的分数。因此这种分数也叫做埃及分数,或者叫单分子分数。在我们现今所使用的分数中,当有2个物品要平均分给3个人的时候,每个人可以取得2个1/3。你可以算成2/3 = 1/3 + 1/3。那么,古埃及的人们,是怎么算的呢?首先,把 2 个物品分成 4 个 1/2,先给每个人 1 个 1/2,剩下的 1 个1/2 再分成 3 等分,均分结果,每人分到 1/2 加 1/2 的 1/3,也就是 1/2 + 1/6 = 2/3。
一个古老的传说是:
老人弥留之际,将家中11匹马分给3个儿子,老大1/2,老二1/4,老三1/6。二分之一是5匹半马,总不能把马杀了吧,正在无奈之际,邻居把自己家的马牵来,老大二分之一,牵走了6匹;老二四分之一,牵走了3匹;老三六分之一,牵走了2匹。一共11匹,分完后,邻居把自己的马牵了回去。即11/12=1/2+1/4+1/6。
埃及分数的一些表示例子:
- 2/3 等价于 1/2 + 1/6
- 6/14 等价于 1/3 + 1/11 + 1/231
- 12/13 等价于 1/2 + 1/3 + 1/12 + 1/156
写一个算法,求埃及分数的表示方法。
算法设计<