Here's a math contest for cashiers (well anyone can enter).
The most common algorithm (or series of computational steps) to making change is known as the "greedy algorithm." You start with the highest denomination coin (the quarter), take out as many as you need before it gets to be too much, move onto the next lowest (dime), rinse, repeat until you get to pennies.
For example, using the greedy algorithm, giving 62 cents back in change will equal:
2 quarters + 1 dime + 0 nickels + 2 pennies
Using the greedy algorithm will yield the lowest number of coins needed for any transaction.
However, as any cashier will tell you, using the greedy algorithm will have you hemorrhaging quarters and will leave your roll of nickels practically untouched.
So let's see who can come up with a new change-making algorithm that satisfies the following requirement:
Per 10 transactions, the cashier is left with as close to no coins as possible.
The algorithm that yields a result closest to 0 total coins (using a standard set of randomly generated numbers) will be the winner.
Make the following assumptions:
1) Half dollar coins and dollar coins do not exist.
2) The decimal price of each order (.01 –.99) is random but never .00.
3) (For the sake of simplicity) no coins are added to the cash drawer (by customers.)
4) A cash drawer contains 1 roll of quarters (x40), 1 roll of dimes (x50), 1 roll of nickels (x40), and 1 roll of pennies (x50).
There is no one "right" answer. I don't even have an algorithm formed yet, so I'll try to think of one myself.
Remember that an algorithm is (simply put) a series of steps.
The most common algorithm (or series of computational steps) to making change is known as the "greedy algorithm." You start with the highest denomination coin (the quarter), take out as many as you need before it gets to be too much, move onto the next lowest (dime), rinse, repeat until you get to pennies.
For example, using the greedy algorithm, giving 62 cents back in change will equal:
2 quarters + 1 dime + 0 nickels + 2 pennies
Using the greedy algorithm will yield the lowest number of coins needed for any transaction.
However, as any cashier will tell you, using the greedy algorithm will have you hemorrhaging quarters and will leave your roll of nickels practically untouched.
So let's see who can come up with a new change-making algorithm that satisfies the following requirement:
Per 10 transactions, the cashier is left with as close to no coins as possible.
The algorithm that yields a result closest to 0 total coins (using a standard set of randomly generated numbers) will be the winner.
Make the following assumptions:
1) Half dollar coins and dollar coins do not exist.
2) The decimal price of each order (.01 –.99) is random but never .00.
3) (For the sake of simplicity) no coins are added to the cash drawer (by customers.)
4) A cash drawer contains 1 roll of quarters (x40), 1 roll of dimes (x50), 1 roll of nickels (x40), and 1 roll of pennies (x50).
There is no one "right" answer. I don't even have an algorithm formed yet, so I'll try to think of one myself.
Remember that an algorithm is (simply put) a series of steps.
Comment