<p>在进入连续增量之前,应尝试根据分母/分子的比率将剩余分数转换为1/n。这使总和更快地收敛到目标分数。您还将发现,当比率不完美时,只需在分母上加1:</p>
<pre><code>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))
</code></pre>
<p>输出:</p>
<pre><code>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
</code></pre>
<p>基于此,可以将其实现为一个递归生成器,只返回要相加的埃及分数的分母(并且运行得更快):</p>
<pre><code>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))
</code></pre>
<p>输出:</p>
<pre><code>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
</code></pre>
<p><strong>最短形式</strong></p>
<p>如果您正在寻找分母最小的最短形式(最少的术语数),则需要递归方法。这是一个递归生成器,它生成最短形式的变量,我们可以从中选择分母和最小的变量:</p>
<pre><code>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)))
</code></pre>
<p>输出:</p>
<pre><code>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
</code></pre>