wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> making change greedily
        
(Message started by: inexorable on Nov 28^th, 2005, 1:42pm)

Title: making change greedily
Post by inexorable on Nov 28^th, 2005, 1:42pm

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?