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)