More money! 1

[chiph]

OK, here's another money-related question (everyone's favorite topic!).

How many ways can you make change for a dollar?

The basic thing to know is that there are 100 pennies to the dollar (kudos to Ben Franklin for decimalization of the currency). For those not from the US, here's our coinage system:

1 penny == 1/100 dollar (also called a cent)
1 nickel == 1/20 dollar, or 5 cents
1 dime == 1/10 dollar, or 10 cents
1 quarter == 1/4 dollar, or 25 cents
1 half-dollar == 1/2 dollar, or 50 cents
1 dollar coin == 1/1 dollar, or 100 cents.

I make no excuses for our coinage names. It gets worse when you actually handle the coins, as the dime is physically smaller than the nickel, despite being worth more -- a perfect example of a legacy system. Hopefully people's answers will be legacy-free!

Chip H.


____________________________________________________________________
If you want to get the best response to a question, please read FAQ222-2244 first

 

[vongrunt]

I got 293 - with (both) ugly combination formula and brute-force.



------
[small]select stuff(stuff(replicate('<P> <B> ', 14), 109, 0, '<.'), 112, 0, '/')[/small]

 

[PHV]

Brute force in VBA:

[white]
Function getNumberOfChanges()
Dim P As Long, N As Long, D As Long, Q As Long, H As Long, C As Long 'Penny, Nickel, Dime, Quarter, Half, Coin
Dim i As Long
For P = 0 To 100
  For N = 0 To 20
    For D = 0 To 10
      For Q = 0 To 4
        For H = 0 To 2
          For C = 0 To 1
            If P + 5 * N + 10 * D + 25 * Q + 50 * H + 100 * C = 100 Then
              i = i + 1
            End If
          Next
        Next
      Next
    Next
  Next
Next
getNumberOfChanges = i
End Function[/white]

? getNumberOfChanges
293

Hope This Helps, PH.
Want to get great answers to your Tek-Tips questions? Have a look at FAQ219-2884 or FAQ181-2886

 

[vongrunt]

BanzaiScript:

[white]<%	@Language = "JScript" %>
<%
for( var cnt=0, i=100; i>=0; i-=100 )
	for( var j=i;j>=0; j-=50 )
		for( var k=j;k>=0; k-=25 )
			for( var l=k;l>=0;l-=10 )
				for( var m=l;m>=0;m-=5, cnt++ );

Response.Write (cnt);
%>[/white]

Only valid combos are checked - innermost loop gets executed exactly 293 times, no more.

------
[small]select stuff(stuff(replicate('<P> <B> ', 14), 109, 0, '<.'), 112, 0, '/')[/small]

 

[chiph]

A recursive solution in C#. I'm working on a Ruby version.

[white]
using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;

namespace DollarChange
{
    public class Form1 : System.Windows.Forms.Form
    {
        private System.Windows.Forms.Label label1;
        private System.ComponentModel.Container components = null;

        public Form1()
        {
            InitializeComponent();
        }

        protected override void Dispose( bool disposing )
        {
            if (disposing)
                if (components != null) 
                    components.Dispose();
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code
        private void InitializeComponent()
        {
            this.label1 = new System.Windows.Forms.Label();
            this.SuspendLayout();
            // label1
            this.label1.Location = new System.Drawing.Point(56, 32);
            this.label1.Name = "label1";
            this.label1.TabIndex = 0;
            this.label1.Text = "label1";
            // Form1
            this.AutoScaleBaseSize = new System.Drawing.Size(5, 13);
            this.ClientSize = new System.Drawing.Size(292, 273);
            this.Controls.Add(this.label1);
            this.Name = "Form1";
            this.Text = "Form1";
            this.Load += new System.EventHandler(this.Form1_Load);
            this.ResumeLayout(false);
        }
        #endregion

        // The main entry point for the application.
        [STAThread]
        static void Main() 
        {
            Application.Run(new Form1());
        }

        // Load event.  Kicks off algorithm
        private void Form1_Load(object sender, System.EventArgs e)
        {
            label1.Text = WaysChangeDollarCoin(100).ToString();
        }

        private int WaysChangePenny()
        {
            return 1;
        }

        private int WaysChangeNickel(int numPennies)
        {
            if (numPennies >= 0)
                return WaysChangeNickel(numPennies - 5) + WaysChangePenny();
            else
                return 0;
        }

        private int WaysChangeDime(int numPennies)
        {
            if (numPennies >= 0)
                return WaysChangeDime(numPennies - 10) + WaysChangeNickel(numPennies);
            else
                return 0;
        }

        private int WaysChangeQuarter(int numPennies)
        {
            if (numPennies >= 0)
                return WaysChangeQuarter(numPennies - 25) + WaysChangeDime(numPennies);
            else
                return 0;
        }

        private int WaysChangeHalfDollar(int numPennies)
        {
            if (numPennies >= 0)
                return WaysChangeHalfDollar(numPennies - 50) + WaysChangeQuarter(numPennies);
            else
                return 0;
        }

        private int WaysChangeDollarCoin(int numPennies)
        {
            if (numPennies >= 0)
                return WaysChangeDollarCoin(numPennies - 100) + WaysChangeHalfDollar(numPennies);
            else
                return 0;
        }
    }
}
[/white]

____________________________________________________________________
If you want to get the best response to a question, please read FAQ222-2244 first

 

[Mike Lewis]

This reminds of the short story, The Gift of the Magi, by William Sydney Porter, better known as O Henry. The story starts:

One dollar and eighty-seven cents. That was all. And sixty cents of it was in pennies. ... Three times Della counted it. One dollar and eighty-seven cents. And the next day would be Christmas.

Did O Henry get it wrong, or was Della mistaken?

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

 

[strongm]

Neither ...

[white]Sixty cents of it was in pennies, and so was the other dollar twenty seven - or, if we don't wan't quite so much change, sixty cents of it was in pennies, so was another 2 cents, and then we had a quarter and a dollar...[/white]

 

[Mike Lewis]

Strongm,

Hmm. An interestng idea.

Mike


__________________________________
Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

 

[GPOTony]

I believe that, at the time the story was written, 2-cent coins were still in circulation.
tr

 

[Mike Lewis]

Hi GPOTony,

Interesting. I never knew there was such a thing as a 2-cent coin.

I see that the coins were minted between 1864 and 1873. I believe all of O Henry's stories were written after about 1904. Do you think it's likely the coins stayed in circulation so long after they stopped being produced? I couldn't find any information on that, one way or the other.

Mike


__________________________________
Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

 

[lespaul]

O Henry may have written the stories after 1904, but were the stories set in a time period that would have used the 2¢ pennies? Would make the story more realistic.....

les

 

[mmerlinn]

2 cent pennies? Is that possible? LOL


mmerlinn

"Political correctness is the BADGE of a COWARD!"

 

[Mike Lewis]

Les,

were the stories set in a time period that would have used the 2¢ pennies? Would make the story more realistic.....

Is see your point, but my impression is that O Henry's stories are all pretty much contemporaneous. But I'm not an expert.

Mike


__________________________________
Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

 

[Tarwn]

I just checked my pocket, I have:
A penny from 1985
A penny from 1964
A penny from 1987
A dime from 2005
A quarter from 1966

So I think someone in 1904 still having coins minted in 1864-73 is quite possible

 

[Mike Lewis]

Tarwin,

So I think someone in 1904 still having coins minted in 1864-73 is quite possible

That sounds plausible.

But it's a pity. It means I won't be able to use my little O Henry story any more. Oh, well ...

Mike




__________________________________
Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

 

[GPOTony]

Apparently, there were both 2- and 3-cent coins issued in the past.
See

http://cgi.ebay.com/1872-Fine-detai...QitemZ8413643868QQcategoryZ3356QQcmdZViewItem

and

http://cgi.ebay.com/ws/eBayISAPI.dl...ssPageName=MERCOSI_VI_ROSI_PR4_PCN_BIX_Stores

for pictures.
tr

 

[Stella740pl]

Tarwin,

So I think someone in 1904 still having coins minted in 1864-73 is quite possible
And much earlier than that, too.
I sometimes find pennies from 30s and 40s, and, I believe, occasionally, from 20s - and they were given me as change in stores, not kept in a piggy bank for decades (I only live in USA for a little more than a decade.)

Mike,

I love O'Henry, read his stories many times in Russian and once in English, and apparently, I never ever tried to recalculate the coins in Della's pockets. Maybe I was not curious enough, and maybe at the time I first read it, there we Soviet coins worth 1, 2, 3, 5, 10, 15, 20 (and no 25), and 50 kopecks (or what are they called in English) - so nothing surprising to me.

 

[Mike Lewis]

Hi Stella,

Good to hear there's another O Henry fan in the house.

About five years ago, I bought a book containing one hundred O Henry stories at a bargain price of one pound. That's one (British) penny ( = approx 1.8 US cent) per story. I've read them all at least twice, so I've got my money's worth.

In Britain, we've had a 2-penny coin since 1971 (before that, the "old penny" was worth about 2.5 new pennies). In the Eurozone, there has been a 2-cent coin since the currency started. It's interesting that the US, where a cent is worth slightly less than our pennies, gets along fine without them.

Mike


__________________________________
Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

 

[Stella740pl]

Hi Mike,

Somewhat off topic.

I felt compelled to read it in English after a relative of mine, also O'Henry fan, said that in her opinion, we loved him so much because we read a very professional and exceptionally talented translations (which IS true), which made them better literature than the original, and there is not much to it when you read it in English.

So after I felt that my English is strong enough to read classical books (at least short stories), I got a book in a library. I got to say, I loved the original almost every bit as much as the familiar from the childhood translation. Moreover, after having lived here for several years, I realized that I hadn't understood some details in their entirety before, from the distance and from the translations, even with all the footnotes and comments.

As for the translations, most books used to be translated in Russian by professional writers, not by professional translators - and that made all the difference in the world. For example, I've got to read three different translations of Shakespeare’s "Hamlet", plus the original (well, to be frank, I didn't finish all of them), and can confidently name my favorite out of the four: the one translated by Boris Pasternak (yes, the author of "Doctor Zhivago").

On the other hand, I once got across an English translation of Pushkin's "Eugene Onegin". It was so horrible, it was hard to recognize.

Bur this should belong to another forum.

 

[draigGoch]

slightly off-subject again, but in the uk the price of copper is booming, apparently.

I heard on the radio that metal is now so costly that the copper in a 2 pence coin is worth 3 pence as scrap metal. That's a 50 per cent profit! But the coins need to be earlier than a certain date!

A computer always does what you tell it to, but rarely does what you want it to.....