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