Copyright © University of Cambridge. All rights reserved.
'The Greedy Algorithm' printed from http://nrich.maths.org/
Rosie discusses this problem:
The Greedy Algorithm always works, because there will always
be a biggest unit fraction less than the one being dealt with,
until you reach a unit fraction.
You can see this by looking at different examples.
If you have $\frac{x}{y}$ then keep dividing $y$ by increasing
whole numbers until the result is less than $x$, say $a$ is the
smallest whole number such that $\frac{y}{a}< x$. (If they are
equal then $\frac{x}{y}$ itself is just a multiple of a unit
fraction). Then $\frac{x}{y}=\frac{1}{a}+\frac{xa-y}{ay}$. The same
process can be used now on $\frac{xa-y}{ay}$ and so on until the
remainder is a unit fraction.
I used the dictionary to find out what an algorithm was. It
said
"A finite set of unambiguous instructions performed in a set
sequence to achieve a goal, especially a mathematical rule or
procedure used to compute a desired result. Algorithms are the
basis for most computer programming."
This means that it is a set of instructions that you follow,
that finish in a specific number of moves.
A Greedy Algorithm is a special kind of algorithm.
"A greedy algorithm is any algorithm that follows the problem
solving tactic of making the locally optimal choice at each stage
with the hope of finding the global optimum."
So you do the best possible thing at each stage, in the hope
of finding the best combination overall.