C++ Sequences of Dimes and Quarters Function?

[kevbo423]

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


}

[booradley60]

You will be using recursion. I think that is what the hints are trying to give away. Have you learned about recursion yet?

[kevbo423]

Yes we have. I don't understand how we're supposed to use recursion though.

[booradley60]

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:

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.

[kevbo423]

I'm starting to understand it a bit more. I don't know what the base cases should be.

[kevbo423]

I don't believe we are supposed to use recursion.

[kevbo423]

Now I am completely lost.

[booradley60]

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.

[kevbo423]

My teacher does not want us to use recursion.

[kevbo423]

Okay I got it using recursion. Can you help convert it to code without using recursion?

if(cost <= 5) {
		return 0;
	}else if(cost == 10 || cost == 25) {
		return 1;
	}else {
		return changeWays(cost - 10) + changeWays(cost - 25);
	}
}

[booradley60]

Ah, (s)he wants you to use this...

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

[kevbo423]

Yeah. I'm not sure how to do it now.

[booradley60]

The trick is to fill the entire array based on just a few known values.

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 ];
}