Re: Change for a Dollar


"Charles Richmond" <frizzle@xxxxxxxxx> wrote in message
news:462EB69C.4070205@xxxxxxxxxxxx
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

This starts with two half dollars and goes down to 100 pennies:

cnt = 0
for ( pen = 0; pen <= 100; pen += 1 ) {
for ( nkl = 0; pen + nkl <= 100; nkl += 5 ) {
for ( dim = 0; pen + nkl + dim <= 100; dim += 10 ) {
for ( qtr = 0; pen + nkl + dim + qtr <= 100; qtr += 25 ) {
for ( hlf = 0; pen + nkl + dim + qtr + hlf <= 100; hlf += 50 ) {
if ( pen + nkl + dim + qtr + hlf == 100 ) {
cnt += 1
printf( "%03d) %d pennies, %d nickels, %d dimes, %d
quarters, %d halves\n", \
cnt, pen, nkl/5, dim/10, qtr/25, hlf/50 )
}
}
}
}
}
}

I just stole the skeleton from Mark P and added simple checks to cut down a
little on run time.

- Anton Treuenfels


.