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.
No comments:
Post a Comment