Computer Science 2611
Spring 2000
Laboratory Assignment 4
Handed out: June 27
Coin changing
Suppose that you need to make a given amount of change, and you would
like to use the fewest coins to do it. The available coins are
quarters, dimes, nickles and pennies. How can you make the change?
One approach is to start by taking as many quarters as you can
without getting too much. For example, to make 64 cents, you take
two quarters, since three quarters would be too much. Notice that,
if you divide 64 by 25, you get a quotient of 2, with a remainder of 14.
Next, take as many dimes as you can without getting too much. If there
is 14 cents left, you need to take 1 dime. Notice that, if you divide
14 by 10, you get a quotient of 1 and a remainder of 4.
Do a similar thing with nickles and pennies.
The assignment
This is an exercise in the use of functions. Write each of the following
as a separate function. Write a clear and concise contract for each
function. The solution that you turn in must have a clear contract
for each function.
- Write a function with a void result type that has two reference
parameters and two value parameters. The value parameters are information
coming into the function. They tell the function an amount of change
that needs to be made, and the worth of a particular coin. The
reference parameters are values coming out of the function. They
should tell the caller how many of that coin to use, and how much
is left over. For example, if the desired amount of change is 82 cents and
the coin value is 25 cents, then the function should say to use 3 coins,
with 7 cents left over.
- Write a function that has a void result type, one value
parameter and four reference parameters. The value parameter is
information coming into the function, and it is an amount of change.
The four reference parameters are information coming out of the
function. They should be set to the number of quarters, dimes,
nickles and pennies (one number per parameter) that should be
used to make the requested amount of change. This function should
use the preceding one.
- Write a function that has no parameters, and has a result type
of int. This function should prompt the user for an amount of change, read
the amount, and return the amount as its value.
- Write a main function that repeatedly reads an amount of
change from the user and prints the number of quarters, dimes, nickles
and pennies to use for that amount of change. Make your program's output
clear and readable, not just raw numbers. The program should continue
asking until a negative number is typed in by the user. At that point,
the program should stop, without saying how many coins to use to
make the negative amount of change.
The main function must use the functions described above to do
the work.
Successive refinement
To develop this program, use successive refinement. Do not
write the entire program and then test it. Instead, write ONE function.
Write a short main program to test that function. Make sure that function
is working before going on to the next function.
Successive refinement is a tool that is an absolute necessity
for writing software. It allows you to isolate mistakes. If each
tool that you create is tested when it is written, then any mistake
is most likely in the most recently written function. This makes
mistakes MUCH easier to find and fix than if the mistake could be
anywhere in a program. If you write an entire program and try to
test it, not only can a mistake be anywhere, but there will surely
be several mistakes, and they will often act together to make it
confusing about where the mistake is located.
Use successive refinement for this program, even if you do not
think that you need it. You will need it later, and will want
experience using it.