counting change algorithm

[OCD]

I need to write a recursive program to count the number of ways to make change from a given number of cents using quarters, dimes, and nickles. I cant figure out what the algorithm is - do you have any advice for me???

[Nepomuk]

I need to write a recursive program to count the number of ways to make change from a given number of cents using quarters, dimes, and nickles. I cant figure out what the algorithm is - do you have any advice for me???

Do you only have to count the possible ways or do you have to list them as well? Here's a hint, on how to count them:

countQuarters(int cents)
{
   If "cents" can be paid with a quarter, add 1 to the amount of possibilities and reduce "cents" by the value of a quarter.
   If there's the value of a quarter or more left, call "countQuarters" and
   if there's the value of a dime or more left, call "countDimes" and
   if there's the value of a nickle or more left, call "countNickles".
}

With that help, you should be able to write a recursive algorithm which does the job.
If you don't only have to count them, you'll have to print out, what you're doing in a suitable format.

Greetings,
Nepomuk

[RedSon]

Do you only have to count the possible ways or do you have to list them as well? Here's a hint, on how to count them:

countQuarters(int cents)
{
   If "cents" can be paid with a quarter, add 1 to the amount of possibilities and reduce "cents" by the value of a quarter.
   If there's the value of a quarter or more left, call "countQuarters" and
   if there's the value of a dime or more left, call "countDimes" and
   if there's the value of a nickle or more left, call "countNickles".
}

With that help, you should be able to write a recursive algorithm which does the job.
If you don't only have to count them, you'll have to print out, what you're doing in a suitable format.

Greetings,
Nepomuk

Nepomuk,

This is borderline spoon feeding, but given the simplicity of the OPs task I can't really think of another way to put it. Maybe without the countQuarters method signature...I don't know. Ahh who cares, they should be able to figure it out easy enough anyway...right?

lol

[Nepomuk]

Nepomuk,

This is borderline spoon feeding, but given the simplicity of the OPs task I can't really think of another way to put it. Maybe without the countQuarters method signature...I don't know. Ahh who cares, they should be able to figure it out easy enough anyway...right?

lol

Believe me, I had much more than that and then reduced it as much as I could without making it completely worthless... But I also remember when I first used recursion and at that time, this task would have seemed quite tricky. Anyway, there's still work to do for the OP and he can hardly do that without understanding the algorithm, can he? ^^

Greetings,
Nepomuk

[OCD]

But how does this algorithm determine the number of ways? doesnt it just determine the least amount of coins needed? shouldnt the algorithm be
Number of ways to change amount A using N kinds of coins =
Number of ways to change amount A using all but the first
kind of coin
+
Number of ways to change amount A - D using all N kinds
of coins, where D is the denomination of the first kind of coin.

[Nepomuk]

But how does this algorithm determine the number of ways? doesnt it just determine the least amount of coins needed? shouldnt the algorithm be
Number of ways to change amount A using N kinds of coins =
Number of ways to change amount A using all but the first
kind of coin
+
Number of ways to change amount A - D using all N kinds
of coins, where D is the denomination of the first kind of coin.

Have another look at what I wrote and maybe think about how you would do the task without a computer - say you had 0.50$ and coins with the values 0.25$, 0.10$ and 0.01$ - how would you find all possibilities?

Greetings,
Nepomuk