Re: Change for a Dollar

On Apr 24, 10:22�pm, Mark P <use...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
Charles Richmond wrote:
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.

I won't speak for you, but I'm certain that these loops do exactly what
*I* think they do.  What do you think they do?



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

I considered writing a follow-up post after I noticed that this is what
you asked for, but then I thought it might make a fun exercise for the
reader to let him (you) figure it out.  But if you want me to ruin that
potential fun, I will.  Simply replace the line ++n_ways; with an
appropriate print statement using the values of n_50, n_25, n_10, n_5
and an appropriately computed value for the number of pennies.

Mark

P.S. Incidentally, I ran my program and it computed 292 ways not 293,
but perhaps Dave considers the original dollar to be the "missing" way?

Isn't a dollar coin considered change?

.

Relevant Pages

  • Re: Change for a Dollar
    ... Charles Richmond wrote: ... thinking about writing a program to list out *all* ... but I'm certain that these loops do exactly what *I* think they do. ... but then I thought it might make a fun exercise for the reader to let him figure it out. ...
    (comp.programming)
  • Re: Speed up matrix multiplication
    ... I am currently writing a program which involves computing the ... Are any of the matrices constant between the loops? ... MATLAB FAQ: http://www.mit.edu/~pwb/cssm/ ...
    (comp.soft-sys.matlab)
  • Reading a variable line by line with while loop
    ... I have been using while loops to read files in line by line when I want ... writing to, ... Later, Ray Parrish ... Writings of "The" Schizophrenic, what it's like to be a schizo, and other ...
    (Ubuntu)
  • Block processing for 2D matrices
    ... The function im2col does exactly what I need, but strangely, I find ... it is running MUCH SLOWER than writing 2 nested "for" loops to index ...
    (comp.soft-sys.matlab)
  • Re: Styles of Speech
    ... writing was being used, but don't know if that speech was common. ... should speak the way people in everyday life speak. ... else we want to show about that society. ... and what historical models they seem to borrow most from. ...
    (rec.arts.sf.written)