Ways to make change 2.

[Astrumjunior]

The Question: Tell the number of possible ways you could have made change, if the amount is $10.00 or less.

What I've done:

#include <iostream>

using namespace std;

int main()
{
int D10, D5, D2, D1, C50, C25, C10, C5, C1;
double amount;
int counter = 0;

cout << "Hello, enter an amount and I will tell you \n";
cout << "the number of ways you could make change.\n";
cin >> amount;

amount *= 100;

for(D10 = 0; D10*10000 <= (amount/1000); D10++)
{
for(D5 = 0; D10*1000 + D5*500 <= (amount/500); D5++)
{
for(D2 = 0; D10*1000 + D5*500 + D2*200 <= (amount/200); D2++)
{
for(D1 = 0; D10*1000 + D5*500 + D2*200 + D1*100 <= (amount/100); D1++)
{
for(C50 = 0; D10*1000 + D5*500 + D2*200 + D1*100 + C50*50 <= (amount/50); C50++)
{
for(C25 = 0; D10*1000 + D5*500 + D2*200 + D1*100 + C50*50 + C25*25 <= (amount/25); C25++)
{
for(C10 = 0; D10*1000 + D5*500 + D2*200 + D1*100 + C50*50 + C25*25 + C10*10 <= (amount/10); C10++)
{
for(C5 = 0; D10*1000 + D5*500 + D2*200 + D1*100 + C50*50 + C25*25 + C10*10 + C5*5 <= (amount/5); C5++)
{
for(C1 = 0; D10*1000 + D5*500 + D2*200 + D1*100 + C50*50 + C25*25 + C10*10 + C5*5 + D1*1 <= (amount/1); C1++)
{
counter++;
} //.01
} //.05
} //.1
} //.25
} //.5
} //1
} //2
} //5
} //10

cout << "In total, there are " << counter << " possible combinations.\n";
system("pause");
}
--------------------------------------------------------------------------------
So, I made this, but when I run the program, it really doesn't display the number of ways. Any idea of what I'am missing?

[jsmith]

In every place you multiple D10 by 1000 except one, where you multiply it by 10,000.

[jsmith]

But your logic is all wrong anyway.

The line "amount *= 100;" implies that amount is the number of cents.
Dividing the number of cents by, say, 1000, yields a value specified in 100s of dollars, which
you are then comparing against D10 * 1000 (assuming you fix the typo) which is cents. The
two units don't match, so the comparison must be wrong.

So after fixing that, it still seems that your program takes an eternity to run. This is because of
the sheer number of multiplications and additions you are doing. Particularly, you have 8 multiplies
and 8 additions in the terminating condition of your inner-most for loop (assuming the multiply by 1
is optimized out). This loop is going to run a gazillion times, so I'm sure your program will take a long
time to generate the answer.

You need to think of a different approach to solving the problem.

I wrote your program using recursion and it completes in 4.3 seconds with no optimization (using gcc)
and 1.1 seconds with -O3.

(The number of ways of making change for $7.37 is 680,592 by the way.)

EDIT: I got it down to just under 0.5 seconds. (btw, this is using $7.37 as the input value).

EDIT 2: LOL. I got it down to less than .01 seconds now. (average = 0.007s)

[Astrumjunior]

I started working with C++ recently, so this is what I came up with. Our teacher had showed us his program and his worked fast, which is why I loss at how to approach this. It may take long but I' am just glad it does what its suppose to do (or come close to), even though its super slow.

Having said that, I appreciate you help! I'll fix it as soon as I can.

I heard of recursion, but I'am barely covering pointers atm (<---sad panda). I don't think we will cover it this semester, but I'll keep working with coding to improve.