C++ Question : Recursively finding the number of ways to make change for a dollar

Factual Questions
1

I’m trying to write a C++ program that uses a recursive function to find the number of possible combinations of pennies, nickels, dimes and quarters to make $1.00 (or any amount of change for that matter)

When i started the program, it seemed deceptively easy… I thought that if you went through subtracting 25 cents from the total and adding the number of possible ways to make a quarter (13) to a counter, and so forth adding the ways to make a dime (4), nickel (2) or anything less than a nickel (1) until there was no change left your answer.

But I found out rather quickly that you can’t add the number of ways, if there’s 13 ways to get a quarter and 2 ways to get a nickel that doesn’t mean there’s 15 ways to get 30 cents. You have to multiply the two (or so I thought). But there’s not 26 combinations either. You quickly run into doubles.

You’re looking for the total number of combinations but the total number of permutations. So i developed a formula for coming up with the number of combinations given the number of possibilities for 2 outcomes.

To get the formula I drew a 4 x 3 rectangle (in the formula an N1 x N2 formula, where N2 <= N1) and labeled the top A-D and the side A-C. Combining the top with the side letter in each cell of the rectangle you get three combinations that have 2 permutations, AB, AC and BC. You’ll also notice that AD is not doubled because the side only goes down to C, meaning there is only one AD.

Anyhow… the formula I came up with is:

N1 * N2 - ( ( N2 ^ 2 - N2) / 2 )

I didn’t even recognize the shortcoming of this formula in this program until I had already coded it out. Here’s the code i came up with:


int change ( int cents )
{
	
	int n1, n2; // postcondition : n1 > n2

	 if ( cents >= 25 )
	 {
	    if ( ( cents - 25 ) > 25 )
		{
			n1 = change (cents - 25);
			n2 = 13;
		}
		else
		{
			n1 = 13;
			n2 = change(cents - 25);
		}

		 return  ( n1 * n2 ) - ( ( n2 ^ 2 - n2 ) / (2) );
	 }
	
	 else if ( cents >= 10 )
	 {
	    if ( ( cents - 10 ) > 10 )
		{
			n1 = change (cents - 10);
			n2 = 4;
		}
		else
		{
			n1 = 4;
			n2 = change(cents - 10);
		}
	 	 return  ( n1 * n2 ) - ( ( n2 ^ 2 - n2 ) / (2) );
	 }
	 else if ( cents >= 5 )
	 {
		n1 = 2;
		n2 = 1;
		 return  ( n1 * n2 ) - ( ( n2 ^ 2 - n2 ) / (2) );
	 }
	 else
		 return 1;
	

}

The problem, however, is that not each possible way to make a certain value is unique when combined with another set of possibilities. For example, when finding the amount of combinations for 30, you have two ways of making a nickel, and 13 ways of making a quarter. If you use this formula, the number of possiblities that aren’t unique is 1, giving you a total of 25. This is wrong, however, because there are quite a few possibilites canceled out because they are not unique. For example, if you make a quarter out of 3 nickels and 10 pennies and you make the nickel out of 5 pennies, this is no different than making the quarter out of 2 nickels and 15 pennies and the nickel by just using a nickel. 2 “different” permutations, but really just one combination.

So, that brings me to the question.

How do I go about doing this?

Any ideas/formulas/code/etc would be greatly appreciated, thanks.

2

Er… input in cents…

Don’t know if this works, but off the top of my head…


int change (int input; int ways)
{
   if (input == 0) return 0;
   if (input == 1) return 1;
   if (input > 1)
   {
      ways = change(input -1, ways);
      ways++;
   }
   if (input > 5)
   {
      ways = change(input -5, ways);
      ways++;
   }
   if (input > 10)
   {
      ways = change(input -10, ways);
      ways++;
   }
   if (input > 25)
   {
      ways = change(input -25, ways);
      ways++;
   }
   return ways;
}
3

Don’t take offense at this, but if this is a homework assignment then please try to work out a solution entirely on your own … although I haven’t thought it through completely, so I’m not sure if this will work :

Put simply : Take n of the largest size coin available, where n increases from 1 each time until equal to or greater than the dollar amount C. Repeat until there are no smaller coins available, or after a solution is found.

Using US currency, you’d take a quarter, and find all solutions that include 1 quarter, then all with 2 quarters, and so on. This way you shouldn’t re-count identical solutions.

So for $1, you’d proceed as follows :

$1.00 quarters = 1.
$0.75 dimes = 1.
$0.65 nickels = 1.
$0.60 pennies = 1,2,3 … 60.

Solutions found : 1

step back up to nickels :
$0.65 nickels = 2.
$0.55 pennies = 1,2,3 … 55.

Solutions found : 2

etc.

panama jack

This is not a sig. It’s just some text written under a bunch of underscores.

4

That should be from 0 each time, to cover all the cases.

panama jack

This is not a sig. It’s just some text written under a bunch of underscores.

5

are you taking into account the 50cent coins?, they may be old, but still leagle tender

6

hint: don’t start with giving a quarter, start with the penny.
the first possibility ennumerated (after 100 recurssions)would be 100 pennys. the others are ennumerated on the way back out of the stack (next being 95 pennies and a nickel).

-luckie

7

I wrote a COBOL ::waiting for guffaws to subside:: program in about half an hour that did this.

Here’s one point though: Most Internet lists say that their are 293 ways to make change for a dollar. Well, there are 293 ways to make change for a dollar bill, but 292 ways to make change for a dollar.