Problem 2126. Split bread like the Pharaohs - Egyptian fractions and greedy algorithm
How would you split 5 loaves of bread among 8 people in all fairness? Get a hint from the Pharaohs. 5/8 = 4/8 + 1/8 , i.e. each receives 1/2 of loaf plus 1/8 - splitting 4 loaves into 1/2 and then the last loaf into 8 pieces.
Egyptian fraction is writing any rational number p/q in terms of unity fractions;
Write a program to return the Egyptian fraction of a given rational number p, q. You outputs in the above cases should be the series of denominator values,
You can use simple greedy algorithm or alternatives.
- AMS blog post by Tyler Clark (@tylermath12) http://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/
- Bonus points if you can enumerate all possible Egyptian fractions of (p,q), but thats a problem for another day.
P.S: Updated test suite to check for proper solutions only
Solution CommentsShow comments
Problem Recent Solvers65