用C埃及分数 [英] Egyptian Fractions in C

问题描述

古埃及人不仅使用形式分数1 / N 因此，任何其他的部分都被重新presented因此单位分数和的总和，而且，所有的单位分数是不同的！

什么是一个很好的方法，使任何部分的古埃及分数（少款项更好）的C或Java中，哪种算法可以使用​​，分支定界，一个*？

例如：

  3/4 = 1/2 + 1/4

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

解决方案

一种方法是贪心算法。考虑到部分 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

The ancient Egyptians only used fractions of the form 1/n so any other fraction had to be represented as a sum of such unit fractions and, furthermore, all the unit fractions were different!

What is a good method to make any fraction an egyptian fraction (the less sums better) in C or java, what algorithm can be used, branch and bound, a*?

for example:

3/4 = 1/2 + 1/4

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

解决方案

One way is the greedy algorithm. Given the fraction f, find the largest Egyptian fraction 1/n less than or equal to f (i.e., n = ceil(1/f)). Then repeat for the remainder f - 1/n, until f == 0.

So for 3/4, you'd compute:

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

And for 6/7:

• n = ceil(7/6) = 2; remainder = 6/7 - 1/2 = 5/14
• n = ceil(14/5) = 3; remainder = 5/14 - 1/3 = 1/42
• n = ceil(42) = 42; remainder = 1/42 - 1/42 = 0
• 6/7 = 1/2 + 1/3 + 1/42

这篇关于用C埃及分数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！