Python中的埃及分数，而循环测试的单位分数不够高

Question

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将访问的最大号码

Answer 1

在进入连续增量之前，应尝试根据分母/分子的比率将剩余分数转换为1/n。这使总和更快地收敛到目标分数。您还将发现，当比率不完美时，只需在分母上加1：

from fractions import Fraction
def egyptFrac(n,d):
    target  = Fraction(n,d)
    result  = []
    fracSum = Fraction(0)
    while fracSum != target:
        remain = target-fracSum
        d,r    = divmod(remain.denominator,remain.numerator)
        frac   = Fraction(1,d+(r>0))
        result.append(frac)
        fracSum += frac
    # return result
    return str(target)+" = "+" + ".join(map(str,result))

输出：

print(egyptFrac(104,105)) # 104/105 = 1/2 + 1/3 + 1/7 + 1/70
print(egyptFrac(4,13))    # 4/13 = 1/4 + 1/18 + 1/468
print(egyptFrac(17,29))   # 17/29 = 1/2 + 1/12 + 1/348
print(egyptFrac(5,121))   # 5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
print(egyptFrac(4,5))     # 4/5 = 1/2 + 1/4 + 1/20
print(egyptFrac(5,12))    # 5/12 = 1/3 + 1/12

基于此，可以将其实现为一个递归生成器，只返回要相加的埃及分数的分母（并且运行得更快）：

from math import gcd
def egyptDenom(N,D):
    d,n = divmod(D,N)
    yield d+(n>0)
    if n==0:return
    n,d = N*(d+1)-D,D*(d+1) 
    yield from egyptDenom(n//gcd(n,d),d//gcd(n,d))

def egyptFrac(N,D):
    return f"{N}/{D} = "+" + ".join(f"1/{d}" for d in egyptDenom(N,D))

输出：

print(egyptFrac(104,105)) # 104/105 = 1/2 + 1/3 + 1/7 + 1/70
print(egyptFrac(4,13))    # 4/13 = 1/4 + 1/18 + 1/468
print(egyptFrac(17,29))   # 17/29 = 1/2 + 1/12 + 1/348
print(egyptFrac(5,121))   # 5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
print(egyptFrac(4,5))     # 4/5 = 1/2 + 1/4 + 1/20
print(egyptFrac(5,12))    # 5/12 = 1/3 + 1/12

最短形式

如果您正在寻找分母最小的最短形式（最少的术语数），则需要递归方法。这是一个递归生成器，它生成最短形式的变量，我们可以从中选择分母和最小的变量：

from fractions import Fraction
def shortEgypt(N,D,maxTerms=None,minD=2):
    if maxTerms is None:
        mt    = 1
        found = False
        while not found:
            mt += 1
            for result in shortEgypt(N,D,mt):
                yield result
                found = True
        return
    d,n = divmod(D,N)
    if n==0 and d>=minD:yield [d]
    if maxTerms<2 or not n: return
    target = Fraction(N,D)
    minD   = max(minD,D//N+1)
    while sum(Fraction(1,minD+i) for i in range(maxTerms))>=target:
        frac   = Fraction(1,minD)
        remain = target-frac
        for rest in shortEgypt(remain.numerator,remain.denominator,maxTerms-1,minD+1):
            yield [minD]+rest
        minD += 1

def shortestEgypt(N,D,select=lambda i:min(i,key=sum)):
    return f"{N}/{D} = "+" + ".join(f"1/{d}" for d in select(shortEgypt(N,D)))

输出：

print(shortestEgypt(104,105)) # 104/105 = 1/2 + 1/3 + 1/7 + 1/70
print(shortestEgypt(4,13))    # 4/13 = 1/4 + 1/26 + 1/52
print(shortestEgypt(17,29))   # 17/29 = 1/3 + 1/4 + 1/348
print(shortestEgypt(5,121))   # 5/121 = 1/33 + 1/121 + 1/363
print(shortestEgypt(4,5))     # 4/5 = 1/2 + 1/5 + 1/10
print(shortestEgypt(5,12))    # 5/12 = 1/4 + 1/6    

Answer 2

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

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))

计算时间几乎是任何分数的眨眼时间