Welcome Guest [Log In] [Register]
Welcome to The New Coffee Room. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
  • Pages:
  • 1
  • 2
Change for a dollar
Topic Started: Dec 7 2011, 04:17 AM (836 Views)
apple
one of the angels
i tested very well in math.. I'd just guess the answers if one didn't have to show the work. I understand equations with 2 variables and really enjoyed geometry..but calculus about killed me. I had to drop the class the first week.. I hadn't a clue. Heck... Algebra 2 about killed me too.

Seriously the happiest day of my life was the end of the 2nd trimester my freshman year in college. I managed to get a D the first two trimesters with the help of a great tutor and forgiving grader. The prof came up to me and said "
Why are you taking Algebra next trimester? I said "Cuz i have to????.

He said "NO - you don't.. all you need is two sessions". I grew wings, I flew across campus, I ran in the streets down to the lake and kept running forever. ... hours at least. I was so ecstatic...

it was better than having a baby or getting married.
it behooves me to behold
Offline Profile Quote Post Goto Top
 
Axtremus
Member Avatar
HOLY CARP!!!
Klaus
Dec 8 2011, 03:46 AM
Horace
Dec 7 2011, 06:57 PM
I'd note that while yours is more conceptually elegant, it doesn't scale well computationally due to the recursion. For the given problem our solutions take about the same amount of time, but for making change for $4, yours takes about 6 times as long, and for $10, yours takes over a thousand times as long. (The answers are always identical because both solutions are correct.)
Recursion is not expensive in properly implemented languages
I saw that coming as soon as I read Horace's comment. :D
Online Profile Quote Post Goto Top
 
big al
Member Avatar
Bull-Carp
A somewhat similar puzzle...

What is the largest monetary value of US coins one can have and be unable to change a dollar bill?

Big Al
Location: Western PA

"jesu, der simcha fun der man's farlangen."
-bachophile
Offline Profile Quote Post Goto Top
 
jon-nyc
Member Avatar
Cheers
1.19?
In my defense, I was left unsupervised.
Online Profile Quote Post Goto Top
 
Klaus
Member Avatar
HOLY CARP!!!
big al
Dec 8 2011, 10:01 AM
A somewhat similar puzzle...

What is the largest monetary value of US coins one can have and be unable to change a dollar bill?

Big Al
Sounds like a special case of the subset sum problem.
Trifonov Fleisher Klaus Sokolov Zimmerman
Online Profile Quote Post Goto Top
 
Horace
Member Avatar
HOLY CARP!!!
Axtremus
Dec 8 2011, 09:35 AM
Klaus
Dec 8 2011, 03:46 AM
Horace
Dec 7 2011, 06:57 PM
I'd note that while yours is more conceptually elegant, it doesn't scale well computationally due to the recursion. For the given problem our solutions take about the same amount of time, but for making change for $4, yours takes about 6 times as long, and for $10, yours takes over a thousand times as long. (The answers are always identical because both solutions are correct.)
Recursion is not expensive in properly implemented languages
I saw that coming as soon as I read Horace's comment. :D
Hey, I love recursion. Used it recently when writing some code to draw a dendrogram to visualize a hierarchical clustering. But it should be used sparingly, only if it increases clarity of expression. The textbook example of calculating factorials is pretty funny in that it's a perfect example of gratuitous recursion. But yes in Klaus' idea it's appropriate.
As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good?
Online Profile Quote Post Goto Top
 
Horace
Member Avatar
HOLY CARP!!!
Klaus
Dec 8 2011, 03:46 AM
Edit: I tried your variant as well and it confirms my suspicion: For $1000 it needs several seconds, and for $5000 I had to kill the process after two minutes. But it is still cool that you managed to find a different correct solution! Recursive divide&conquer is so deeply baked into my brain that I suck at imperative&iterative solutions :lol2:
Thanks Klaus, I appreciate that.
As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good?
Online Profile Quote Post Goto Top
 
Klaus
Member Avatar
HOLY CARP!!!
Horace
Dec 8 2011, 12:27 PM
Hey, I love recursion. Used it recently when writing some code to draw a dendrogram to visualize a hierarchical clustering. But it should be used sparingly, only if it increases clarity of expression. The textbook example of calculating factorials is pretty funny in that it's a perfect example of gratuitous recursion.
I don't agree, of course :lol2: Recursion is more general than loops, and in those cases where the same can be expressed with a loop, recursion is as efficient, thanks to tail call optimization. Which version is more clear is to a large degree just determined by what programmers are used to, although there is a lot of evidence that it is easier to reason about the correctness of functional recursion than of imperative loops.

If you don't like the recursive factorial definition, you should definitely read this :cool2:

That said, 95% of the loops or recursions that programmers write are unnecessary anyway because the same algorithm could be expressed more concisely using higher-order recursion/looping operators, such as map, fold, unfold etc. I sometimes wonder how many unnecessary non-termination bugs we have to suffer in our software just because programmers are not able to use looping combinators.
Trifonov Fleisher Klaus Sokolov Zimmerman
Online Profile Quote Post Goto Top
 
RosemaryTwo
Member Avatar
HOLY CARP!!!
apple
Dec 8 2011, 08:38 AM
i tested very well in math.. I'd just guess the answers if one didn't have to show the work. I understand equations with 2 variables and really enjoyed geometry..but calculus about killed me. I had to drop the class the first week.. I hadn't a clue. Heck... Algebra 2 about killed me too.

Seriously the happiest day of my life was the end of the 2nd trimester my freshman year in college. I managed to get a D the first two trimesters with the help of a great tutor and forgiving grader. The prof came up to me and said "
Why are you taking Algebra next trimester? I said "Cuz i have to????.

He said "NO - you don't.. all you need is two sessions". I grew wings, I flew across campus, I ran in the streets down to the lake and kept running forever. ... hours at least. I was so ecstatic...

it was better than having a baby or getting married.
This post deserves some love. Funny stuff.

Apple I had math tutors in college, too. My husband tutored me through depreciation in federal income tax.

He also, ahem, helps the boys with math homework.
"Perhaps the thing to do is just to let stupid run its course." Aqua
Offline Profile Quote Post Goto Top
 
RosemaryTwo
Member Avatar
HOLY CARP!!!
apple
Dec 8 2011, 08:38 AM
i tested very well in math.. I'd just guess the answers if one didn't have to show the work. I understand equations with 2 variables and really enjoyed geometry..but calculus about killed me. I had to drop the class the first week.. I hadn't a clue. Heck... Algebra 2 about killed me too.

Seriously the happiest day of my life was the end of the 2nd trimester my freshman year in college. I managed to get a D the first two trimesters with the help of a great tutor and forgiving grader. The prof came up to me and said "
Why are you taking Algebra next trimester? I said "Cuz i have to????.

He said "NO - you don't.. all you need is two sessions". I grew wings, I flew across campus, I ran in the streets down to the lake and kept running forever. ... hours at least. I was so ecstatic...

it was better than having a baby or getting married.
This post deserves some love. Funny stuff.

Apple I had math tutors in college, too. My husband tutored me through depreciation in federal income tax.

He also, ahem, helps the boys with math homework.
"Perhaps the thing to do is just to let stupid run its course." Aqua
Offline Profile Quote Post Goto Top
 
big al
Member Avatar
Bull-Carp
jon-nyc
Dec 8 2011, 10:38 AM
1.19?
Right you are. Three quarters, four dimes, and four pennies.

Big Al
Location: Western PA

"jesu, der simcha fun der man's farlangen."
-bachophile
Offline Profile Quote Post Goto Top
 
Horace
Member Avatar
HOLY CARP!!!
By the way, if anybody's curious about the sorts of thought processes which lead to Klaus' answer, here's a textbook which gives this exact question and his exact answer as an example of a cool recursion:

Structure and Interpretation of Computer Programs from MIT Press

This particular recursion appears to have been a textbook example for 30 years or more.
As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good?
Online Profile Quote Post Goto Top
 
« Previous Topic · The New Coffee Room · Next Topic »
Add Reply
  • Pages:
  • 1
  • 2