C中的埃及分数
古埃及人只使用1/nforms的分数，因此任何其他分数必须表示为这些单位分数的总和，而且，所有单位分数都不同！
在C或java中使任何分数成为埃及分数（越少越好）的好方法是什么，可以使用什么算法，分支和绑定，a *？
例如：
3/4 = 1/2 + 1/4 6/7 = 1/2 + 1/3 + 1/42
一种方法是贪心算法。 给定分数f ，找到小于或等于f的最大埃及分数1/n （即，n = ceil（1 / f））。 然后重复余数f - 1/n ，直到f == 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
从埃及部分裁剪
我是怎么想出这些价值观的？ 好吧，我估计单位分数最大的分数比给定分数小。 我从给定的分数中减去了这个单位分数。 如果这个余数仍不是单位分数，我重复该过程，选择小于该余数的最大单位分数。 这个过程可以一遍又一遍地重复。
我们以7/8为例。 我们估计7/8有2/3（最大单位分数小于7/8）。 我们减去7/8 – 2/3，即5/24，不能简化为单位分数。 因此我们估计5/24为1/5（最大单位分数小于5/24）。 我们减去5 / 24-1 / 5，得到1/120，这是一个单位分数。 所以，7/8 = 2/3 + 1/5 + 1/120。
对于a / b ，使MAX a * b。
取MAX的素数因子（这是prime_fac（a）和prime_fac（b）的并集以及这两个列表中的每一个的倍数）并迭代它们，从低位开始变为高位。
那些是你可能的1 / x。
编辑：哦，是的！ 别忘了考虑2/3 ！
您在网站上提出了一个问题，人们通常会在答案中提供代码。 代码没有其他答案，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