Re: Change for a Dollar
- From: Duncan Muirhead <dmuir@xxxxxxxxx>
- Date: Wed, 25 Apr 2007 11:40:49 +0100
On Tue, 24 Apr 2007 13:20:47 -0500, Charles Richmond wrote:
I heard one night on David Letterman that there areI think it's easiest to get the design of recursive procedure
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???
right if you generalise a bit. Suppose you have n coin values
C[0]..C[n-1], in increasing order. If W( S, m) is the number of ways
of making change for S using coins up to the m'th, we have
W(S,m) = Sum{ i>=0 with i*C[m]<S | W(S-i*C[m], m-1)}
This translates into code that takes a fraction of a second on
my (very ordinary) pc. If you want to generate a list of all
the ways its very similar, except you are concatenating strings
instead of adding numbers.
.
- References:
- Change for a Dollar
- From: Charles Richmond
- Change for a Dollar
- Prev by Date: Re: random integer
- Next by Date: Re: bignum with floating point
- Previous by thread: Re: Change for a Dollar
- Next by thread: Re: Change for a Dollar
- Index(es):
Relevant Pages
|
