We did almost this exact problem earlier this year on my course at uni but using the functional language ML, and actually returning a list of lists of ways to make the change. The solution is really neat in ML and since I have exams in a month or so I thought it wouldn't be such a bad idea for me to go over it and try to explain it to the other monks. I'll give the code first and then try and explain what it does.
1. fun change (till, 0) = []
2. | change (, amt) = 
3. | change (coin::till, amt) =
4. if amt < coin then change(till, amt)
6. let fun allchange  = 
7. | allchange (cs::css) = (coin::cs) :: allchange css
8. in allchange (change (coin::till, amt - coin)) @ change (til
The first line starts our function declaration and matches the input pattern of some list of coins that we can use (till
) and an amount left over to make of 0. There is exactly one way to do this, an empty list of coins, so we return a list (the outer set of square brackets) containing the empty list (the inner set of square brackets). Line 2 is a second base case: we have run out of suitable types of coin, but we still need to make change. In this case there are no solutions so we return the empty list. From here onwards we get into the recursive magic, the case where we have a list of coins (the first of which is called coin
, the rest of the list being contained in till
) and an amount
we are aiming to make. If the coin at the front of the list is too big, we simply discard it and try making change for that amount using the other coins in the till with a recursive call to change(till, amount)
(line 4). Otherwise we define a new function allchange
which takes a list of lists (cs
is a list of coins, css
is a list of such lists) and adds a coin
to the front of all lists of coins in that list (line 7). We then call allchange
on all the solutions found by the recursive call to change(till, amt-coin)
and append (@
) it to the list of ways of simply making change from coin
(ie always taking the biggest coin we can).
Hopefully that makes sense, all the magic happens in line 8. It seemed like a pretty neat solution and short even in comparison with the Perl ones on offer (even if you do have to invest more brain power to understand it).
My cow-orkers were talking in punctuation the other day. What disturbed me most was that I understood it.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] ||