Re: OT: making change

There is a very interesting article on this subject here: http://www.sciencenews.org/articles/20030510/mathtrek.asp.

The article makes a few interesting points. One is that the US coin system would become more efficient (in number of coins needed to provide transaction change) if an 18 cent piece were introduced to replace the dime. Keep the dime, and introduce a 32 cent coin for even greater transaction efficiency. ...though this is going to be harder for your high-school student clerks to add in their heads.

It also mentions that the "greedy algorithm" (starting from the largest denomination and working downward) provides the most efficient (in number of coins used) solution for US coin denominations, but isn't guaranteed to do so given the denominations of other countries.

Dave

Comment on Re: OT: making change

Replies are listed 'Best First'.
Re: OT: making change by Dominus (Parson) on Nov 24, 2004 at 16:16 UTC
Says davido: the US coin system would become more efficient (in number of coins needed to provide transaction change) if an 18 cent piece were introduced to replace the dime. I looked into this in some detail eight or nine years ago. It turns out that there are two optimal systems, assuming that you want to have four coins. One system has a penny, a nickel, a quarter, and a glubbernog, which is worth 18 cents. With this system, you can expect to carry an average of only 3.88 coins at any time; the current system averages 4.69 coins. The other optimal system replaces the quarter with a 29-cent snonkularb. Among 5-coin systems, the optimal one has a penny, a nickel, and coins of denominations 16, 23, and 33 cents; under this system, you can expect to carry an average of only 3.28 coins at any time rather than 4.19 with the current system. (Notice that 4.19 is exactly half a coin less than if you disregard half dollars; that's because half the time you are carrying at least two quarters and can replace them with a half dollar, saving one coin.) The current system could be substantially improved by replacing the mostly-useless half dollar with a 32 or 33-cent coin; this would cut the average to 3.45 or 3.48 coins. Of course, the real goal is to minimize weight and bulk, not number of coins. The obvious solution here is to make the quarters really small. Hope this helps. -- Mark Dominus Perl Paraphernalia	[reply]
Re^2: OT: making change by Ovid (Cardinal) on Nov 24, 2004 at 16:20 UTC
Why is C so powerful? It can optimize computer time. Why is Perl so powerful? It can optimize programmer time. An 18 or 32 cent piece seems the equivalent of C. I prefer Perl :) Cheers, Ovid New address of my CGI Course.	[reply]