Have you ever wondered what’s the best way to count change? Learn how a computer would do it!
Suppose you need to count out five dollars and thirty two cents in change. Would you count out five hundred and thirty two pennies? Probably not! In order to be efficient as possible, you’d count a $5 bill, a quarter, a nickel, and two pennies. In general, you always want to make change with the smallest possible number of coins and bills; counting change back in this manner reduces the chance of error, since you have fewer items to deal with.
A Simple Algorithm
This observation - that we would like to deal with as few items as possible - immediately leads to a very simple algorithm for counting
change: just add the largest bill (or coin) possible and go from there! In computer science, we call this a recursive algorithm: we just keep doing the same thing over and over (on ever-decreasing problem sizes) until the entire problem has been solved. Written formally, the algorithm looks like this:
Let CHANGE be the amount of money to be given back
While CHANGE is at least $100, give the customer a $100 bill and subtract $100 from CHANGE
While CHANGE is at least $20, give the customer a $20 bill and subtract $20 from CHANGE.
If CHANGE is at least $10, give the customer a $10 bill and subtract $10 from CHANGE.
If CHANGE is at least $5, give the customer a $5 bill and subtract $5 from CHANGE.
While CHANGE is at least $1, give the customer a $1 bill and subtract $1 from CHANGE.
While CHANGE is at least 25 cents, give the customer a quarter and subtract 25 cents from CHANGE.
While CHANGE is at least ten cents, give the customer a dime and subtract 10 cents from CHANGE.
If CHANGE is at least five cents, give the customer a nickel and subtract five cents from CHANGE.
While CHANGE is at least one cent, give the customer a penny and subtract one cent from CHANGE.
Notice that each “while” statement is executed over and over until the condition is no longer true; in other words, you never give a $20 bill until the remaining amount of change due is less than $100. Also, notice that we have “if” statements rather than “while” statements where a condition can only be true once; we will never give more than one $10 bill, for example, because if we had two $10 bills we could replace them with a $20 bill.
Now, Practice It!
Practicing counting change back is easy; set a price, take some amount of money greater than that price, and follow the above algorithm. When you’re finished, check that no set of coins or bills can be combined to make a larger one; for example, you should never have more than four pennies, because five pennies makes a dime; you should never have two dimes and a nickel or you could have made a quarter. If this condition is met and the total amount of change plus the item price add up to the original amount of money, you have solved the problem correctly!
