埃及分数

发表于 | 更新于 | 分类于

在看科普视频的时候学到了埃及分数和贪婪算法，这里用code实现一下。

埃及分数

古埃人使用的是象形文字，他们用这样的符号表示分数

image

image

他们在圈圈下面画几个竖线代表几分之一，还有几个规定好的分数有特殊的符号，分数有无数多个，不可能给所有分数都画上符号，所以古埃及人把任意分数都表示为不同的单位分数的和，就是分子为1，分母为各不相同的正整数。任何正有理数都能表达成这一个形式。

例如：

$1=\frac12+\frac13+\frac16$

1还可以表示为：

$1=\frac12+\frac13+\frac19+\frac1{18}$

接下使用贪婪算法来生成任意一个正有理数的埃及分数形式。

贪婪算法

贪婪算法：将一项分数分解成若干项单分子分数后的项数最少，称为第一种好算法；最大的分母数值最小，称为第二种好算法。 例如：

${\displaystyle {\frac {2}{7}}={\frac {1}{4}}+{\frac {1}{28}}}$。共2项，是第一种好算法，比${\displaystyle {\frac {2}{7}}={\frac {1}{5}}+{\frac {1}{20}}+{\frac {1}{28}}}$的项数要少。

又例如，${\displaystyle {\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}}比 {\displaystyle {\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{759}}+{\frac {1}{208725}}}$ 的最大分母要小，所以是第二种好算法。

找出仅小于${\displaystyle r={\frac {a}{b}}}$的最大单位分数。这个分数的分母的计算方法是：即用${\displaystyle b}$除以${\displaystyle a}$，舍去余数，再加1。（如果没有余数，则${\displaystyle r}$已是单位分数。）
把${\displaystyle r}$减去单位分数，以这个新的、更小的${\displaystyle r}$重复步骤1。

例子：把${\displaystyle {\frac {19}{20}}}$转成单位分数。

${\displaystyle \lfloor 20\div 19\rfloor =1}$，所以第1个单位分数是${\frac {1}{2}}$；

${\displaystyle {\frac {19}{20}}-{\frac {1}{2}}={\frac {9}{20}}}$；

${\displaystyle \lfloor 20\div 9\rfloor =2}$，所以第2个单位分数是${\displaystyle {\frac {1}{3}}}$；

${\displaystyle {\frac {9}{20}}-{\frac {1}{3}}={\frac {7}{60}}}$；

${\displaystyle \lfloor 60\div 7\rfloor =8}$，所以第3个单位分数是${\displaystyle {\frac {1}{9}}}$；

${\displaystyle {\frac {7}{60}}-{\frac {1}{9}}={\frac {1}{180}}}$已是单位分数。

所以结果是：
${\displaystyle {\frac {19}{20}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{9}}+{\frac {1}{180}}}$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 寻找最大公约数
def _gcd(a, b):
    # Supports non-integers for backward compatibility.
    while b:
        a, b = b, a%b
    return a

# 约分
def ReduceFraction(numerator, denominator):
    if type(numerator) is int is type(denominator):
        g = _gcd(numerator, denominator)
        if denominator < 0:
            g = -g
        else:
            g = _gcd(numerator, denominator)
        numerator //= g
        denominator //= g
    return (numerator, denominator)

# 分数减法
def SubFraction(a, b):
    an, ad = a
    bn, bd = b
    numerator = an*bd - ad*bn
    denominator = ad * bd
    return ReduceFraction(numerator, denominator)

# 埃及分数生成器返回分母的list
def EgpytFraction(numerator=0, denominator=None, ret=[]):
    a = (denominator // numerator) + 1
    ret.append(a)
    t = SubFraction((numerator, denominator), (1, a))
    if t[0] == 1:
        ret.append(t[1])
        return ret
    return EgpytFraction(t[0], t[1], ret=ret)
EgpytFraction(5, 121, ret)
[25, 757, 763309, 873960180913, 1527612795642093418846225]

总结

埃及分数的表示不是唯一的，但应该有一个项数最少的表达式，我们把这个叫做最优的，但目前还没有一个算法可以求出最优的埃及分数。

0%