Re: Making Change
- To: mathgroup at smc.vnet.net
- Subject: [mg15178] Re: [mg15160] Making Change
- From: Jurgen Tischer <jtischer at col2.telecom.com.co>
- Date: Fri, 18 Dec 1998 02:10:55 -0500
- Organization: Universidad del Valle
- References: <199812160811.DAA24583@smc.vnet.net.>
- Sender: owner-wri-mathgroup at wolfram.com
Wilson,
I've never seen a penny, but that doesn't mean too much since I live in
Colombia. I own a dollar coin, from a trip to Vegas 20 years ago. There
have to be half dollar coins, I cannot imagine Clint Eastwood dropping
a nickel at the bar. So:
In[1]:= coins={100,50,25,10,5,1};
In[2]:= add[li_,tot_]:=Append[li,tot-li.Take[coins,5]]/;Length[li]==5
In[3]:= add[li_,tot_]:=
add[#,tot]&/@(
Append[li,#]&/@
Range[0,Quotient[tot-li.Take[coins,Length[li]],
coins[[Length[li]+1]]]])
In[4]:= allChange[tot_]:=Flatten[add[{},tot],4]
I won't show you the 293 ways of changing a dollar in all its glory,
help yourself.
In[5]:= allChange[100]
To know the number use Length.
In[6]:= numberChanges0[x_]:=Length[allChange[x]]
In[7]:= numberChanges0[100]
Out[7]= 293
If you are only interested in the number without listing all solutions,
this will do it a bit faster (even with this speedup I hadn't the nerve
to wait for 1000).
In[8]:= numberChanges[x_,1]=1;
In[9]:= numberChanges[x_,n_]:=
Sum[numberChanges[x-k coins[[-n]],n-1],{k,0,Quotient[x,coins[[-n]]]}]
In[11]:= numberChanges[x_]:=numberChanges[x,6]
In[12]:= numberChanges[100]
Out[12]= 293
Jurgen
PS: Don't get a wooden nickel.
Wilson Figueroa wrote:
>
> Hello Group,
>
> I have a question pertaining to making change.
>
> I was reading The Bathroom Trivia Book and came across the following
> statement:
>
> There are 293 ways to make change for a dollar.
>
> In the book Introduction to Programming with Mathematica by Gaylord,
> Kamin and Wellin there is the following routine:
>
> makeChange[x_]:=Quotient[Drop[FoldList[Mod,x,{25,10,
> 5,1}],-1],{25,10,5,1}]
>
> that will use he fewest of each coin to make change.
>
> is there a way to modify this so that it will enumerate the 293 ways of
> making change for a dollar or any number of bills?
>
> For example, for $1.00 the output would show
>
> 100, pennies
> 95 pennies, 1 nickel
> 90 pennies, 1 dime
> 90 pennies, 2 nickels
>
> ..
> ..
> ..
>
> and then tell me there are 293 such enumerations.
>
> Thank you for any help.
>
> Wilson
>
> *** Posted from RemarQ - http://www.remarq.com - Discussions Start Here
> (tm) ***
- References:
- Making Change
- From: flip@aznet.net (Wilson Figueroa)
- Making Change