Famously (or at least famously in maths puzzle circles) there are 293 ways to make a US dollar using the following coins:
Penny (1 cent) | Nickel (5 cents) | Dime (10 cents) | Quarter (25 cents) | Half Dollar (50 cents) | Dollar (100 cents)
You could make a dollar with, for example, 4 quarters or 10 dimes.
How many ways are there of making a Brtish pound?
At the time of writing GB currency has the following coins
1p, 2p, 5p, 10p, 20p, 50p and £1 or 100p.
It’s usually a good idea to start problems like this by looking at simpler cases.
If we only have 1p coins, the answer is easy. There’s only 1 way to make any value: 1p = 1, 2p = 1 + 1, 3p = 1 + 1 + 1 etc
How about if we have 1p and 2p coins?
| Value | Possible | Ways |
|---|
| 1p | 1p | 1 |
| 2p | 2 x 1p, 2p | 2 |
| 3p | 3 x 1p, 2p + 1p | 2 |
| 4p | 4 x 1p, 2p + 2p, 2p + 1p + 1p | 3 |
| 5p | 5 x 1p, 2 x 2p +1p, 2p + 3 x 1p | 3 |
Extend the table and you quickly see a pattern
| Value | Ways |
|---|
| 1p | 1 |
| 2p | 2 |
| 3p | 2 |
| 4p | 3 |
| 5p | 3 |
| 6p | 4 |
| 7p | 4 |
| 8p | 5 |
| 9p | 5 |
| 10p | 6 |
We could write the following python code to work out the number of ways of making values with only 1 or 2p coins:
def coin12(n):
if n%2 == 0:
return int(n/2 +1)
else:
return int((n + 1)/2)
What about if we have 1p, 2p and 5p coins?
It turns out we can use our previous function to help us work this out.
For example, we could make 8p entirely of 2s and 1s. But this is just coin12(8) ways using the above function
We could make 8p using a 5p coin and 3p made of 2s and 1s: this is coin12(3) ways
This lets us write out the following table.
| Value | Possible | Ways |
|---|
| 1p | coin12(1) | 1 |
| 2p | coin12(2) | 2 |
| 3p | coin12(3) | 2 |
| 4p | coin12(4) | 3 |
| 5p | 5p, coin12(5) | 4 |
| 6p | 5p + 1p, coin12(6) | 5 |
| 7p | 5p + coin12(2), coin12(7) | 6 |
| 8p | 5p + coin12(3), coin12(8) | 7 |
| 9p | 5p + coin12(4), coin12(9) | 8 |
| 10p | 5p + 5p, 5p + coin12(5), coin12(10) | 10 |
We can use this to help us write a new function
def coin125(n):
total =0
while n >= 5:
total += coin12(n)
n -= 5
return total + coin12(n)
When the function is tested, the results match the table above.
for i in range (1,11):
print(i ,": " ,coin125(i))
Now we can look at using the 1p, 2p, 5p and 10p coins. Our coin125 function suggests a way this can be done:
def coin12510(n):
total =0
while n >= 10:
total += coin125(n)
n -= 10
return total + coin125(n)
Similarly we could make functions for coins up to 20p, 50p and 100p
I’ve missed out some of the steps below, but working through all the coins I finished up with the following function:
def coin125102050100(n):
total =0
while n >= 100:
total += coin125102050(n)
n -= 100
return total + coin125102050(n)
print(coin125102050100(100))
Which gave me the correct answer: 4563. In other words, there are 4,563 ways to make £1 using 1p, 2p, 5p, 10p, 20p, 50p and £1 coins.
However.
This isn’t very elegant. Looking at the code we can see we’re doing the same thing over and over again. Also, what if we had a currency that used 100 coins? Or 1000? It would take a lot of copying and pasting to work those problems out.
There has to be a better way.
Let’s look at the functions again. It’s easy to spot a pattern to them. Using pseudocode, they can be written out something like this:
define coinVALUES(n):
total =0
while n >= VALUE:
total += coinVALUES-1(n)
n -= VALUE
end while
return total + coinVALUES-1(n)
end define
Here’s a first attempt at writing the above in Python
values = [100, 50, 20, 10, 5, 2, 1]
def coin(n, val):
total = 0
while n> values[val]:
total += coin(n, val+1)
n -= values[val]
return total + coin(n, val+1)
You might notice I’ve written a recursive function, but there’s a problem. There’s no escape clause, there’s nothing to stop the function calling itself forever.
That’s quite easy to fix though
All we have to do is realise that coin1(n) = 1. If you want to make 5p using only 1p coins, there’s only one way to do it: 1p + 1p + 1p + 1p + 1p.
We can use that to add a clause to make a proper recursive function.
It also sorts out an irritating niggle: why should coin12 be different to all the other coin functions?
values = [100, 50, 20, 10, 5, 2, 1]
def coin(n, val):
if values[val] == 1:
return 1
total = 0
while n>= values[val]:
total += coin(n, val+1)
n -= values[val]
return total + coin(n, val+1)
print(coin(100,0))
This works but it’s a little bit messy. I have to call the function with an extra argument, 0, telling it to start at the beginning of the values list.
It would be better to treat coin as a “helper” function and to write another function to call it. This would make the function a lot more user friendly.
I’ve wrapped the coin function in a one called makechange. To show the flexibility of my function, I’ve used makechange to work out how many ways there are to make change from a dollar.
values = [100, 50, 25, 10, 5, 1]
def coin(n, val):
if values[val] == 1:
return 1
total = 0
while n>= values[val]:
total += coin(n, val+1)
n -= values[val]
return total + coin(n, val+1)
def makechange(n):
return coin(n,0)
print(makechange(100))