I'm completely lost with this function I'm supposed to write. My Comp Sci teacher is terrible. I appreciate any help.
// changeWays:
// counts the number of sequences of dimes and quarters
// that add up to a particular total
// e.g. 60 cents can be supplied four different ways:
// 25+25+10, 25+10+25, 10+25+25, 10+10+10+10+10+10
// Hint: How many ways can I get my result if I first insert a dime?
// How many ways can I get my result if I first insert a quarter?
int changeWays( int cost )
{
int arr[100] = {0}; // enough array spaces for up to 500 cents
// To make best use of this array, divide values by 5
// so 75 cents would be represented at subscript 75/5
We're going to define a function that gives us a count of all the ways we can make change with dimes and quarters. Looks like you want to call it int changeWays( int cost );
Hint: How many ways can I get my result if I first insert a dime?
How many ways? Well, I have a function that will tell me that. If I start with a dime, then that means the number of ways I can make change is changeWays( costYouGaveMe - dimeAmount ); where dimeAmount is probably a constant that equals 10.
How many ways can I get my result if I first insert a quarter?
How many ways? Well, I have a function that will tell me that. If I start with a quarter, then that means the number of ways I can make change is changeWays( costYouGaveMe - quarterAmount); where quarterAmount is probably a constant that equals 25.
That's the recursion for the general case. The hard part about recursion is specifying your base cases. Think about the problem in this way, and see how far you can get with some code. In pseudocode:
1 2 3 4 5 6 7 8 9 10 11 12
changeWays( cost )
{
waysToMakeChange <- 0
//if we start with a dime
waysToMakeChange += changeWays( cost - DIME_AMOUNT )
//if we start with a quarter
waysToMakeChange += changeWays( cost - QUARTER_AMOUNT )
return waysToMakeChange
}
NOTE: THE BASE CASES ARE NOT ACCOUNTED FOR IN THIS PSEUDOCODE. If you were to just write this into valid C++ form you would get infinite recursion, which will overflow your call stack and blow up.
As you recursively call the function, you are passing smaller and smaller amounts (since when we call the function, we are saying some cost MINUS some amount). Eventually, when the amout you pass to the function gets small enough, you're going to find yourself in a few discrete cases where it won't make sense to pull off another dime (cost - DIME_AMOUNT) or another quarter (cost - QUARTER_AMOUNT). What will those cases look like? What do you do when you get to those cases? Either you'll end up with exactly 10 cents left, or exactly 25 cents left, or some amount that you just can't make change with using only dimes and quarters. Think about how to detect and handle these cases. The whole idea of a base case is that once you hit one, you DON'T do another recursive call of your function.
int arr[100] = {0}; // enough array spaces for up to 500 cents
// To make best use of this array, divide values by 5
// so 75 cents would be represented at subscript 75/5
int changeWays( int cost )
{
//if cost isn't divisible by 5 then we won't be able to use it to index our special array
if(cost % 5 != 0) return 0;
// To make best use of this array, divide values by 5
// so 75 cents would be represented at subscript 75/5
int arr[100] = {0}; // enough array spaces for up to 500 cents
arr[0] = 0; //can't make change for 0 cents
arr[1] = 0; //can't make change for 5 cents
arr[2] = 1; //this represents a dime (only one way to make 10 cents)
arr[5] = 1; //this represents a quarter (only one way to make 25 cents)
//based on these initial values we need to generate the rest of arr in a loop
//...
//grab the index that corresponds to what the user passed in
return arr[ cost/5 ];
}