HELP WITH RECURSION! 
Author Message
 HELP WITH RECURSION!

Hi.  I am having a very difficult time understanding a certain problem which
we encountered in a programming book.  I was wondering if anyone had any ideas
on how to go about doing the following :

Write a recursive method to solve the following problem: given c cents, n
nickels, d dimes, and q quarters, how many ways can you make change for m
cents?  For example, if c= 10, n= 10, d= 10, and m=5, you can make change in 2
ways : use 5 pennies or 1 nickel.  Your method may assume that all parameters
are either 0 or positive integers.

Any code/ideas would be appreciated infinately!
Thanks,
-Jay LeBoeuf



Sat, 17 Apr 1999 03:00:00 GMT  
 HELP WITH RECURSION!

Gaia dhuit,


Quote:
>given c cents, n
>nickels, d dimes, and q quarters, how many ways can you make change for m
>cents?  

I'm not a Yanqui so I have to assume 1 quarter = 25 cents, 1 dime = 10 cents,
and 1 nickel = 5 cents.

My Algorithm :

If m is 0 then finish
Divide 25 into m. Call the result y.
if y <= q then
        Say "I'll give y quarters"
        Get the remainder from the division, call it m.
        Do My Algorithm again.
end-if
Divide 10 into m. Call the result y.
if y <= d then
        Say "I'll give y dimes"
        Get the remainder from the division, call it m.
        Do My Algorithm again.
end-if
Divide 5 into m. Call the result y.
if y <= n then
        Say "I'll give y nickels"
        Get the remainder from the division, call it m.
        Do My Algorithm again.
end-if
Divide 1 into m. Call the result y.
if y <= c then
        Say "I'll give y cents"
        Get the remainder from the division, call it m.
        Do My Algorithm again.
end-if
Say "End of this change-combination"
End Of My Algorithm.

Suggestions for optimization :

(-) Use c instead of english.

(1) Division by 1 is obviously silly.

(2) The similarity of the 4 stages suggests a loop, possibly using arrays with
the values { 25, 10, 5, 1 } and { "quarters", "nickels", "dimes", "cents" }

(3) Should you do (1) <b>and</b> (2) ?

(4) It's dumb to say "I'll give 0 quarters".

(5) What happens if your boss says
"We need this to work for 46 different currencies, in 5 minutes" ?
As bosses have been known to say.

(They also say things like "And it should work for users who have no sense".
But don't worry about that one. you're only still learning, and you don't have
to listen to that yet.)

And remember Jackson's rules of optimization (apocryphal) :

        Rule 1 : Don't optimize
        Rule 2 : Don't optimize now.
        Rule 3 : Get a faster machine.

PS - Thank you to the book (or homework assigner ?) - Nice problem.

---
Janus

http://www.iol.ie/~jab

Gaia leat



Sun, 18 Apr 1999 03:00:00 GMT  
 HELP WITH RECURSION!

Quote:

> Hi.  I am having a very difficult time understanding a certain
> problem which we encountered in a programming book.  I was wondering
> if anyone had any ideas on how to go about doing the following :
> Write a recursive method to solve the following problem: given c
> cents, n nickels, d dimes, and q quarters, how many ways can you
> make change for m cents?  For example, if c= 10, n= 10, d= 10, and
> m=5, you can make change in 2 ways : use 5 pennies or 1 nickel.
> Your method may assume that all parameters are either 0 or positive
> integers.

If you have difficulties implementing your solution, post the relevant
part of the source code here and we will help you.  But we won't do
your homework.

--

IBM European Networking Center . . . VNET: GEHLERT at MAZVM01
Telecooperation Department . . . .  Phone: +49-6221-59-4429 (FAX -3300)
Vangerowstr. 18 . . . . . . . . . . . ITN: *142-4429
D-69118 Heidelberg

Quote:
>>> Opinions are my own, not those of IBM. <<<



Sun, 18 Apr 1999 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Help on recursion

2. novice needs help with recursion

3. Newbie needs help w/ recursion

4. Help with recursion and parameter passing

5. help - VSS Recursion Flag

6. Help with recursion and pointers building doubly linked list from a binary tree.

7. Fibonacci recursion using dynamic stacks (HELP)

8. HELP ME ON RECURSION PLEASE

9. help please; recursion

10. URGENT HELP WITH TREES and recursion

11. HELP with balancing braces program using recursion.

12. Recursion help!

 

 
Powered by phpBB® Forum Software