java - C 中的埃及分数

Question

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

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

例如:

3/4 = 1/2 + 1/4

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

Answer 1

一种方法是贪心算法。给定分数 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