Re: Change for a Dollar

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?
.

Relevant Pages

  • 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)
  • Re: Change for a Dollar
    ... I won't speak for you, but I'm certain that these loops do exactly what ... I considered writing a follow-up post after I noticed that this is what ...
    (comp.programming)
  • 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)