Let Me Count The Ways, aside from
being a poem by Elizabeth Barrett Browning, is also a reference to
a classical programming algorithm in which a programmer is required
to write an application which will calculate how many ways change
can be made for a specific amount. The problem uses 1¢, 5¢, 10¢,
25¢ and 50¢ coins (any number of each) and, for any amount in
change, there will be a unique number of combinations to provide
that amount.
For example, to make 26¢ in
change, there are 13 possible combinations of coins, consisting
of:
| Solution |
1 |
5 |
10 |
25 |
| 1 |
1 |
|
|
1 |
| 2 |
1 |
1 |
2 |
|
| 3 |
1 |
3 |
1 |
|
| 4 |
1 |
5 |
|
|
| 5 |
6 |
|
2 |
|
| 6 |
6 |
2 |
1 |
|
| 7 |
6 |
4 |
|
|
| 8 |
11 |
1 |
1 |
|
| 9 |
11 |
3 |
|
|
| 10 |
16 |
|
1 |
|
| 11 |
16 |
2 |
|
|
| 12 |
21 |
1 |
|
|
| 13 |
26 |
|
|
|
Notice particularly that each
of the solutions includes at least one 1¢ piece (1 penny). If the
required change were only 25¢, how many solutions would there be?
(Careful, this could be a trick question.)
And now for the first
problem. You've seen the example so -- now -- can you program
your internal computer to figure out how many combinations there
are to create the following four amounts:
Obviously, we
don't need a 50¢ piece for any of these
And, for your second problem,
using the same 1¢, 5¢, 10¢, 25¢ and 50¢ coins, determine the
minimum number of coins (no bills allowed) required to make
change in the following amounts:
| E |
F |
G |
H |
I |
| 52¢ |
91¢ |
$1.24 |
$2.07 |
$2.33 |
The cache is located at:
N AH° FD.DAC / W CDD° AH.DGC