Greedy Algorithm
A Greedy Algorithm is one that always chooses the best immediate option. The advantage is that it usually makes decisions simpler, but it may create problems in the long run. It is useful for making programs that don't take long to run. Do not use it in your everyday life.
Contents
[hide]How to use
If you're solving a math problem, and it involves something similar or the same as egyptian fractions, Step : Find the largest fraction with a denominator of a positive integer.
Step : Subtract the number you got from () from the original fraction.
Step : Repeat until you get a fraction with numerator .
Example
Problem
If , , and are positive integers, and , what is ?
Solution using the Greedy Algorithm
Let . Obviously, as the denominator decreases, the fraction increases. Therefore, . The least possible value of is . Then, . Again, we find the least possible value of , which is . We subtract to get . Therefore, . Our answer is then .