Help with a C++ Program?

I need to create a c++ program that will give the number of different ways to break a dollar. For example, you can change a dollar to:





1.) 4 quarters


2.) 10 dimes


3.) 20 nickels


4.) 2 quarters and 3 dimes and 4 nickels


5.) etc....





I need ideas on how to create the program. So, the program should prompt the user to enter a dollar amount ($2, $5, etc) and the program should give a number of how many different ways you can give it.

Help with a C++ Program?
Use the Greedy Algorithm:


1) First fit as many of the largest denomination you can into the break.


2) Fill in the remaining with the next largest denomination, continue until you get to the penny denomination.





This is you first answer. (From which all your other answers are derived)





Loop:


Start from the lowest breakable denomination, break one of it into the next denomination. Then two, then three etc.


(This would be your first level set of answers)





Recursion:


Recursively break larger denominations into smaller ones. (i.e. Quarters can be broken to dimes which can be broken to nickels etc.)





Note:


You may need to address the fact that quarters don't break perfectly into dimes by either:


- breaking 2 quarters for every 5 dimes


- filing quarter greedy algorithm answers and dime greedy algorithm answers separately.








An example of the greedy algorithm is linked in the 2nd source sources section.
Reply:culture_nine, can you provide a sample source code.

sympathy flowers