Copyright © University of Cambridge. All rights reserved.

## 'The Greedy Algorithm' printed from http://nrich.maths.org/

### Show menu

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.