6

古埃及人只使用分数形式1/n，因此任何其他分数都必须表示为这些单位分数的总和，而且，所有单位分数都是不同的！

在C或java中使任何分数成为埃及分数（越少越好）的好方法是什么，可以使用什么算法，分支定界，a *？

例如：

3/4 = 1/2 + 1/4

6/7 = 1/2 + 1/3 + 1/42
4

4 回答 4

8

一种方法是贪心算法。给定分数，找到小于或等于（即 n = ceil(1/f)）f的最大埃及分数。然后重复余数，直到。1/nff - 1/nf == 0

因此，对于 3/4，您将计算：

  • n = ceil(4/3) = 2 ; 余数 = 3/4 - 1/2 = 1/4
  • n = ceil(4) = 4 ; 余数 = 1/4 - 1/4 = 0
  • 3/4 = 1/2 + 1/4

对于 6/7：

  • n = ceil(7/6) = 2 ; 余数 = 6/7 - 1/2 = 5/14
  • n = ceil(14/5) = 3；余数 = 5/14 - 1/3 = 1/42
  • n = ceil(42) = 42 ; 余数 = 1/42 - 1/42 = 0
  • 6/7 = 1/2 + 1/3 + 1/42
于 2011-03-20T06:03:48.450 回答
3

从埃及分数中裁剪

我是如何得出这些价值观的？好吧，我估计了最大单位分数的分数，它刚好小于给定分数。我从给定的分数中减去了这个单位分数。如果这个余数仍然不是单位分数，我重复这个过程，选择小于这个余数的最大单位分数。这个过程可以一遍又一遍地重复。

让我们以 7/8 为例。我们估计 7/8 和 2/3（最大单位分数小于 7/8）。我们减去 7/8 - 2/3，即 5/24，不能简化为单位分数。所以我们用 1/5 来估计 5/24（最大单位分数小于 5/24）。我们减去 5/24-1/5，得到 1/120，这是一个单位分数。所以，7/8=2/3 + 1/5 + 1/120。

于 2011-03-20T06:00:19.327 回答
2

对于a / b，使 MAX a * b。

取 MAX 的主要因子（它是 prime_fac(a) 和 prime_fac(b) 的并集以及这两个列表中的倍数）并遍历它们，从低到高。

这些是你可能的 1/x。

编辑：哦，是的！不要忘记考虑2/3！

于 2011-03-20T05:54:58.887 回答
1

您在一个网站上提出了一个问题，人们通常在该网站的答案中提供代码。代码没有其他答案，C 和 Java 不是我的专长，所以这里有一些 Python 代码。

#! /usr/bin/env python3
import fractions
import functools
import math


def main():
    f = fractions.Fraction(3, 4)
    e = to_egyptian_fractions(f)
    print(*e, sep=' + ')
    f = fractions.Fraction(6, 7)
    e = to_egyptian_fractions(f)
    print(*e, sep=' + ')
    f = fractions.Fraction(7654, 321)
    e = to_egyptian_fractions(f)
    print(*e, sep=' + ')


def validate(function):
    @functools.wraps(function)
    def wrapper(fraction):
        total = fractions.Fraction(0)
        for egyptian in function(fraction):
            if 1 not in {egyptian.numerator, egyptian.denominator}:
                raise AssertionError('function has failed validation')
            yield egyptian
            total += egyptian
        if total != fraction:
            raise AssertionError('function has failed validation')
    return wrapper


@validate
def to_egyptian_fractions(fraction):
    quotient = math.floor(fraction.numerator / fraction.denominator)
    if quotient:
        egyptian = fractions.Fraction(quotient, 1)
        yield egyptian
        fraction -= egyptian
    while fraction:
        quotient = math.ceil(fraction.denominator / fraction.numerator)
        egyptian = fractions.Fraction(1, quotient)
        yield egyptian
        fraction -= egyptian


if __name__ == '__main__':
    main()

也许其他人在编写自己的实现时发现这作为一个简单的指南很有用。上面的程序处理值大于 1 的分数并产生以下输出。

1/2 + 1/4
1/2 + 1/3 + 1/42
23 + 1/2 + 1/3 + 1/92 + 1/29532
于 2016-05-03T16:28:26.163 回答