C中的埃及分数

Question

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

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

例如:

3/4 = 1/2 + 1/4

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

Answer 1

一种方法是贪心算法.给定分数f,找到1/n小于或等于的最大埃及分数f(即,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