Re: Change for a Dollar

Mark P wrote:
Charles Richmond wrote:
I heard one night on David Letterman that there are
293 ways to make change for a dollar. So I started
thinking about writing a program to list out *all*
the ways a dollar could be broken into change. I
just can *not* seem to get a hold on this problem.

I wrote a program with a recursive function attempting
to make the change, but it had excessive runtime and
does *not* seem to be working in any case...

Does anyone have an idea how I can proceed???

There are smarter ways to do it but a brain dead simple approach that ought to be fast enough on any machine built in the last twenty years...

int n_ways = 0;
for( n_50 = 0; n_50 <= 2; ++n_50)
for( n_25 = 0; n_25 <= 4; ++n_25)
for( n_10 = 0; n_10 <= 10; ++n_10)
for( n_5 = 0; n_5 <= 20; ++n_5)
if( n_50 * 50 + n_25 * 25 + n_10 * 10 + n_5 *5 <= 100)
++n_ways;


This may *count* the number of ways change can be made. I am
*not* sure that these loops do what you (or I) think they do.

But for my program, I want to *list* all the ways of making
change. So lines of the list might be:

1) 100 pennies, 0 nickels, 0 dimes, 0 quarters, and 0 halves

......

58) 55 pennies, 2 nickels, 1 dimes, 1 quarter, and 0 halves


For the sake of this program (and David Letterman ;-), we can
only use pennies, nickels, dimes, quarters, and halves. David
is *not* smart enough to know about 2 and 3 cent pieces. ;-)

--
+----------------------------------------------------------------+
| Charles and Francis Richmond richmond at plano dot net |
+----------------------------------------------------------------+
.

Relevant Pages

  • Re: How do I avoid writing the Byte Order Mark ?
    ... How do I avoid writing the Byte Order Mark? ... validator is complaining about the mark. ... the BOM is not part of the file data. ...
    (microsoft.public.dotnet.languages.vb)
  • Re: Compassionare Conservatism
    ... You know civilisation is in serious trouble when this sort of writing ... "Almost all intellectuals profess to love ... humanity and to be working for its improvement and happiness. ... Just out of curiosity, what would you do regarding conservative/right-leaning publications, Mark, since you think that "civilisation is in serious trouble when this sort of writing starts to ...
    (alt.usage.english)
  • Re: How do... YOU... do... "IT"?
    ... Which starts with about half a dozen scene headings, ... >point is very much 'blank page, start writing, see where we ... I draw a large circle and mark off the quarter hours. ... It works quite well to have key turning points around the quarter mark ...
    (rec.arts.sf.composition)
  • Re: Mark Purdey has Passed Away
    ... Writing something meaningful about someone who has died is difficult beyond ... I never met Mark, but had read most of his writings and we did correspond. ... What value praise on ... Mark made some seemingly outrageous claims about harassment. ...
    (uk.business.agriculture)
  • Re: OT: Todays Odd Thought
    ... Is there anyone here who appreciates the writing of Mark Twain... ... This morning I came across this witty remark made by Mark Twain, ... My wife can still make me rapidly lose interest in all other distractions whenever she decides to show the other side of that coin by demonstrating that although clothes may maketh the man, *removing* clothes maketh the woman. ...
    (alt.support.diabetes)