Re: Change for a Dollar

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;

-Mark
.

Relevant Pages

  • Re: Change for a Dollar
    ... Fred Kleinschmidt wrote: ... thinking about writing a program to list out *all* ... 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... ...
    (comp.programming)
  • Re: Change for a Dollar
    ... thinking about writing a program to list out *all* ... 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... ...
    (comp.programming)
  • Re: Doing The Narrative Drains
    ... any reason for it not to be an interesting, complex, multilayered story. ... ought to write differently when you're obviously not enjoying yourself? ... or the one my characters demanded. ... a different application than your writing of first draft, ...
    (rec.arts.sf.composition)
  • Re: Couch Potato
    ... You ought to consider the possibility that your obsession ... with me and my every word may be a mental health issue. ... Now don't be scared, muttley, it's only writing. ...
    (misc.writing)
  • Re: Easter seems to be the time ...
    ... On one side of the coin, I want to get people's reactions to the draft ... So you ought to go and read the whole thing and fix the ... writing and send the draft out to the first batch of agents now. ... much of the polishing and rethinking when you were stuck earlier, ...
    (rec.arts.sf.composition)