The Problem

Calculating change is something that we have been trained to dofrom a young age. For example, without thinking about it, we allknow how many quarters, dimes, nickels and pennies we shouldreceive if the change from our purchase is 47 cents. In this lab,you will write a program to convert a given amount of money (incents) into change.

Notice, however, that there are many ways to calculate change.That is, if our change is 47 cents, we could use 47 pennies. Or wecould use 3 dimes and 17 pennies. Or we could use 4 dimes, anickel, and 2 pennies. You get the idea. What we would really liketo do is use a minimal number of coins. For 47 cents, one way touse a minimal number of coins is 1 quarter, 2 dimes, and 2pennies.

For this lab, you will implement a greedy solution for theproblem of calculating change. What isa greedy solution? It is quite simple. Assumeyou want to convert an arbitrary number of cents into coins of thefollowing denominations: dollar, half-dollar, quarter, dime,nickel, and penny. Use as many dollar coins as possible; then, onwhat's left over, use as many half-dollar coins as possible; thenagain as many quarters as possible; then as many dimes as possible;then as many nickels as possible; finally the remainder is inpennies.