Java – Egyptian scores in C

The ancient Egyptians only used fractions in the form of 1 / N, so any other fractions must be expressed as the sum of these unit fractions, and all unit fractions are different!

What is a good way to make any score an Egyptian score (the less the better) in C or Java, and what algorithms, branches and bindings can be used, a *?

For example:

3/4 = 1/2 + 1/4

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

Solution

One method is greedy algorithm Given the score F, find the maximum Egyptian score 1 / N less than or equal to f (i.e., n = ceil (1 / F)) Then repeat the remainder f – 1 / N until f = = 0

So for 3 / 4, you have to calculate:

> 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

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