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

--

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

 Page 1 of 1 [ 3 post ]

Relevant Pages