MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Making Change


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) ***


  • Prev by Date: Solving with restrictions on parameters
  • Next by Date: Re: NIntegrate of a Decaying Exponential
  • Previous by thread: Making Change
  • Next by thread: Re: Making Change