时间戳

首页 > 解决方案 > Python中的埃及分数，而循环没有测试足够高的单位分数

python - Python中的埃及分数，而循环没有测试足够高的单位分数

问题描述

from fractions import Fraction
n = 103
d = 104
nd = Fraction(n, d)
d1 = 1
while nd != 0:
    d1 = d1 + 1
    if Fraction(1, d1) <= nd:
        testfrac = Fraction(1, d1)
        nd = nd - testfrac
        print(testfrac)

试图计算埃及分数。它适用于更平滑的计算，但当 while 循环必须继续测试更高的数字时效率不够。while 循环将继续运行但最终停止，并且不会测试此计算的最后两个部分。d1 是否有最大数量？

标签： python

解决方案

您应该查看其他算法，以了解人们如何在合理的时间内解决这些问题。我发现 Rosettacode.org 上的 Python 实现非常快。这是基于那边的一个最小版本：

from fractions import Fraction
from math import ceil
  
def ef(fr):
    ans = []
    if fr >= 1:
        if fr.denominator == 1:
            return [[int(fr)], Fr(0, 1)]
        intfr = int(fr)
        ans, fr = [[intfr]], fr - intfr
    x, y = fr.numerator, fr.denominator
    while x != 1:
        ans.append(Fraction(1, ceil(1/fr)))
        fr = Fraction(-y % x, y* ceil(1/fr))
        x, y = fr.numerator, fr.denominator
    ans.append(fr)
    return ans

ef(Fraction(2,3))
ef(Fraction(5,8))
ef(Fraction(103,104))

对于任何分数，计算时间都是一眨眼的功夫。

推荐阅读