Change Variations Help

[bcmst3k]

I'm working on a program for school that gives the most efficient change for a dollar value, and if the value is <= $10.00 it gives the number of variations to make that value of change; for example there are 13 ways to make 25 cents. I have it giving the most efficient change properly however I am having trouble getting past the quarter for the number of variations, as well I'm not sure how to get values lower than the first for loop, currently $.50. Should I do the nested loops separately for each coin denomination, ie a nested loop string starting with quarter, and another with $1.00 etc? Any help would be much appreciated, here's what I have thus far:

#include<iostream>
#include<iomanip>
using namespace std;

void change (double);
void changeNumbers (double);

int main()
{
	double money;
	
	//Get money value and validate.
	do	
	{
	cout << "Enter the value to be changed:  $";
	cin >> money;
	} while (money < 0);
	
	//Run most effecient change function
	change (money);

	//Run number of change variations function
	if (money <= 10.00)
		changeNumbers (money);
	
	system("pause.exe");
	return 0;
}

void change (double money)
{
	int fifties, hundreds, twenties, fives, ones, twos, tens;
	int fiftycents, quarters, dimes, nickels, pennies;
	double value; //To display original movey value again
	value = money;

	//Make calculations for change
	money*= 100;
	hundreds = money / 10000;
	money = money - (10000 * hundreds);
	fifties = money / 5000;
	money = money - (5000 * fifties);
	twenties = money / 2000;
	money = money - (2000 * twenties);
	tens = money / 1000;
	money = money - (1000 * tens);
	fives = money / 500;
	money = money - (500 * fives);
	twos = money / 200;
	money = money - (200 * twos);
	ones = money / 100;
	money = money - (100 * ones);
	fiftycents = money / 50;
	money = money - (50 * fiftycents);
	quarters = money / 25;
	money = money - (25 * quarters);
	dimes = money / 10;
	money = money - (10 * dimes);
	nickels = money / 5;
	money = money - (5 * nickels);
	pennies = money / 1;
	money = money - (1 * pennies);

	//Display denominations with values
	cout << endl;
	cout << "The most effecient way to make $" 
		<< fixed << setprecision (2) << value << " is:" << endl;
	if (hundreds != 0)
	cout << left << setw(20) << "Hundreds:  " << hundreds << endl;
	if (fifties != 0)
	cout << left << setw(20) << "Fifties:  " << fifties << endl;
	if (twenties != 0)
	cout << left << setw(20) << "Twenties:  " << twenties << endl;
	if (tens != 0)
	cout << left << setw(20) << "Tens:  " << tens << endl;
	if (fives != 0)
	cout << left << setw(20) << "Fives:  " << fives << endl;
	if (twos != 0)
	cout << left << setw(20) << "Twos:  " << twos << endl;
	if (ones != 0)
	cout << left << setw(20) << "Ones:  " << ones << endl;
	cout << endl;
	if (fiftycents != 0)
	cout << left << setw(20) << "Fifty Cent Pieces:  " << fiftycents << endl;
	if (quarters != 0)
	cout << left << setw(20) << "Quarters:  " << quarters << endl;
	if (dimes != 0)
	cout << left << setw(20) << "Dimes:  " << dimes << endl;
	if (nickels != 0)
	cout << left << setw(20) << "Nickels:  " << nickels << endl;
	if (pennies != 0)
	cout << left << setw(20) << "Pennies:  " << pennies << endl;
	cout << endl;	
}

void changeNumbers (double money)
{
	int variations = 0,	fives, ones, twos, tens;
	int fiftycents, quarters, dimes, nickels, pennies;
	double value;	//To display money total at the end.
	value = money;


	//Start with most efficient change
	money *= 100;
	tens = money / 1000;
	money = money - (1000 * tens);
	fives = money / 500;
	money = money - (500 * fives);
	twos = money / 200;
	money = money - (200 * twos);
	ones = money / 100;
	money = money - (100 * ones);
	fiftycents = money / 50;
	money = money - (50 * fiftycents);
	quarters = money / 25;
	money = money - (25 * quarters);
	dimes = money / 10;
	money = money - (10 * dimes);
	nickels = money / 5;
	money = money - (5 * nickels);
	pennies = money / 1;
	money = money - (1 * pennies);

	for ( ; fiftycents !=0; fiftycents--, variations++)
	{
		quarters += 2;
		for ( ; quarters != 0 ; quarters--, variations++)
		{
			dimes +=2;
			nickels +=1;
			for ( ; dimes !=0 ; dimes--, variations++)
			{
				nickels += 2;
				for ( ; nickels != 0 ; nickels --, variations++);
				{	
					pennies += 5;
					for (; pennies !=0 ; variations ++)
						pennies /= 5;
				}
			}
		}					
	}
	cout << "There are " << variations << " ways to make change for $";
	cout << fixed << setprecision (2) << value << endl << endl;

}

.cpp attached for ease.
Thanks everyone
-Brian

[Zlatko]

Hello Brian.

What an interesting question!
The problem with the logic is that in your nested loops, each loop wont execute unless you have at least enough money to have one coin of a denomination. Since your first loop is for the fifty cents denomination, it wont run unless you have at least 50 cents.

The point is that you don't need nested loops. You need separate loops for each denomination and you need to go from pennies on up. While you have more than 5 pennies, reduce the penny count and add to the nickel count. Then do the nickels. While you have more than 2 nickels, reduce the nickel count by 2 and add to the dime count. Now the trick. Every time you add to coins of dime or larger, you need to convert everything of smaller denomination back to pennies, and start all over again. So all your denomination loops are put one after the other into a larger loop.

Here is the sequence of converting pennies to a quarter.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 5 1 1 1 1 1 1 1 1 1 1
5 5 5 5 1 1 1 1 1
5 5 5 5 5
10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... adding a dime, change everything else back to pennies
10 5 1 1 1 1 1 1 1 1 1 1
10 5 5 1 1 1 1 1
10 5 5 5
10 10 1 1 1 1 1 ... adding a dime, change everything else back to pennies
10 10 5
25

Is that enough of a hint for you ?

I would say get rid of the floating point values and do everything in term of pennies with integers, then convert to dollars and cents for printout if you like.

Let us know how you do.

[bcmst3k]

Got it. That makes alot more sense now and I'm sure I can program that. Thanks alot for the help (and specifically NOT doing the code for me). I will try and knock that out and post the new code once its done.

Thanks again for the help!
-Brian

[bcmst3k]

Alright, I took the advice and the program is now up to Fifty cent pieces and working correctly. It is outputting the correct variations ($.025 - 13, $.50 - 50, etc). Thanks again for the help. Here is the final code up to .50 cent pieces:

#include<iostream>
#include<iomanip>
using namespace std;

void change (double);
void changeNumbers (double);

int main()
{
	double money;
	char answer;

	do
	{
		//Get money value and validate.
		do	
		{
		cout << "Enter the value to be changed:  $";
		cin >> money;
		} while (money < 0);
	
		//Run most effecient change function
		change (money);

		//Run number of change variations function
		if (money <= 10.00)
			changeNumbers (money);

		cout << "Would you like to run this program again (Y/N)?";
		cin >> answer;
		cout << endl;
	} while (answer == 'y' || answer == 'Y');
	
	system("pause.exe");
	return 0;
}

void change (double money)
{
	int fifties, hundreds, twenties, fives, ones, twos, tens;
	int fiftycents, quarters, dimes, nickels, pennies;
	double value; //To display original movey value again
	value = money;

	//Make calculations for change
	money*= 100;
	hundreds = money / 10000;
	money = money - (10000 * hundreds);
	fifties = money / 5000;
	money = money - (5000 * fifties);
	twenties = money / 2000;
	money = money - (2000 * twenties);
	tens = money / 1000;
	money = money - (1000 * tens);
	fives = money / 500;
	money = money - (500 * fives);
	twos = money / 200;
	money = money - (200 * twos);
	ones = money / 100;
	money = money - (100 * ones);
	fiftycents = money / 50;
	money = money - (50 * fiftycents);
	quarters = money / 25;
	money = money - (25 * quarters);
	dimes = money / 10;
	money = money - (10 * dimes);
	nickels = money / 5;
	money = money - (5 * nickels);
	pennies = money / 1;
	money = money - (1 * pennies);

	//Display denominations with values
	cout << endl;
	cout << "The most effecient way to make $" 
		<< fixed << setprecision (2) << value << " is:" << endl << endl;
	if (hundreds != 0)
	cout << left << setw(20) << "Hundreds:  " << hundreds << endl;
	if (fifties != 0)
	cout << left << setw(20) << "Fifties:  " << fifties << endl;
	if (twenties != 0)
	cout << left << setw(20) << "Twenties:  " << twenties << endl;
	if (tens != 0)
	cout << left << setw(20) << "Tens:  " << tens << endl;
	if (fives != 0)
	cout << left << setw(20) << "Fives:  " << fives << endl;
	if (twos != 0)
	cout << left << setw(20) << "Twos:  " << twos << endl;
	if (ones != 0)
	cout << left << setw(20) << "Ones:  " << ones << endl;
	cout << endl;
	if (fiftycents != 0)
	cout << left << setw(20) << "Fifty Cent Pieces:  " << fiftycents << endl;
	if (quarters != 0)
	cout << left << setw(20) << "Quarters:  " << quarters << endl;
	if (dimes != 0)
	cout << left << setw(20) << "Dimes:  " << dimes << endl;
	if (nickels != 0)
	cout << left << setw(20) << "Nickels:  " << nickels << endl;
	if (pennies != 0)
	cout << left << setw(20) << "Pennies:  " << pennies << endl;
	cout << endl;	
}

void changeNumbers (double money)
{
	int variations = 1,	fives, ones, twos, tens;
	int fiftycents = 0, quarters = 0, dimes = 0, nickels = 0, pennies;
	
	pennies = money * 100;

	for (; pennies >= 5 ; variations++, nickels++, pennies -= 5);
		
	for (; nickels >= 2 ; variations++)
	{
		dimes++;
		nickels -= 2;
		pennies = nickels*5;
		nickels = 0;

		for (; pennies >= 5 ; variations++, nickels++, pennies -= 5);
	}
			
	for ( ; (dimes == 2 && nickels == 1) || dimes >=3 ; variations++)
	{
		quarters++;
		dimes -=2;
		nickels -=1;
		pennies = (dimes * 10);
		pennies += (nickels *5);
		dimes = 0;
		nickels = 0;
		for (; pennies >= 5 ; variations++, nickels++, pennies -= 5);
		
		for (; nickels >= 2 ; variations++)
		{
			dimes++;
			nickels -= 2;
			pennies = nickels*5;
			nickels = 0;
			for (; pennies >= 5 ; variations++, nickels++, pennies -= 5);
		}
	}

	for (; quarters >= 2; variations++)
	{
		fiftycents++;
		quarters -=2;
		pennies += (quarters*25);
		pennies += (dimes * 10);
		pennies += (nickels *5);
		quarters = dimes = nickels = 0;
		for (; pennies >= 5 ; variations++, nickels++, pennies -= 5);
		
		for (; nickels >= 2 ; variations++)
		{
			dimes++;
			nickels -= 2;
			pennies = nickels*5;
			nickels = 0;
			for (; pennies >= 5 ; variations++, nickels++, pennies -= 5);
		}
			
		for ( ; dimes >=2 && nickels > 0 ; variations++)
		{
			quarters++;
			dimes -=2;
			nickels -=1;
			for (; pennies >= 5 ; variations++, nickels++, pennies -= 5);
		
			for (; nickels >= 2 ; variations++)
			{
				dimes++;
				nickels -= 2;
				pennies = nickels*5;
				nickels = 0;
				for (; pennies >= 5 ; variations++, nickels++, pennies -= 5);
			}
		}
	}

	cout << "There is/are " << variations << " way(s) to make change for $";
	cout << fixed << setprecision (2) << money << endl << endl;
}

(maybe a little much for an Intro to Programming class?)