古埃及人不仅使用形式分数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![趣味探究 神奇的 埃及分数 适合4 6年级](https://p.xsw88.cn/allimgs/daicuo/20230911/2711.png)
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/4And 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相关推荐
最新文章