Author |
Topic: making change greedily (Read 620 times) |
|
inexorable
Full Member
Posts: 211
|
 |
making change greedily
« on: Nov 28th, 2005, 1:42pm » |
 Quote  Modify
|
A system of coins is called "nice" if it can represent any amount of money and the greedy algorithm -- repeatedly take the largest coin that will fit -- for making change always uses the smallest number of coins possible. The American system of coins -- 1, 5, 10, 25, 50 -- is nice since, for any number of cents A, the greedy algorithm for breaking A into a combination of coins will use the minimal number of coins. For example, a greedy breakdown of $1.38 is 2 half-dollars, a quarter, a dime, and then 3 pennies, and $1.38 cannot be obtained in fewer than 7 coins. Any total can be made by using only pennies.
The old British coin system is another matter. It consisted of a halfpenny, a penny, threepence, sixpence, a shilling (12 pence), a florin (24 pence), a half-crown (30 pence), a crown (60 pence), and a pound (240 pence). We ignore here the guinea, worth 252 pence. And let us take the indivisible unit as the halfpenny. This system is not nice: a greedy approach to 48 pence would use three coins (half-crown + shilling + sixpence), while it can be done using just two florins.
Question:i) What is the largest coin in this system whose removal leads to a nice system?
ii)give an algorithm to determine whether a system is nice or not?
|
|
 IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print