BASIC ELEMENTS OF JAVA - Java Programming: From Problem Analysis to Program Design - page 91

PROGRAMMING EXAMPLE: Make Change
Write a program that takes as input any change expressed in cents. It should then
compute the number of half-dollars, quarters, dimes, nickels, and pennies to be
returned, using as many half-dollars as possible, then quarters, dimes, nickels, and
pennies, in that order. For example, 483 cents would be returned as 9 half-dollars, 1
quarter, 1 nickel, and 3 pennies.
Input: Change in cents
Output: Equivalent change in half-dollars, quarters, dimes, nickels, and pennies

2

Suppose the given change is 646 cents. To find the number of half-dollars, you
divide 646 by 50 , the value of a half-dollar, and find the quotient, which is 12 , and
the remainder, which is 46 . The quotient, 12 , is the number of half-dollars, and the
remainder, 46 , is the remaining change.
Next, divide the remaining change by 25 , to find the number of quarters. The
remaining change is 46 , so division by 25 gives the quotient 1 , which is the number
of quarters, and a remainder of 21 , which is the remaining change. This process
continues for dimes and nickels. To calculate the remainder (pennies) in integer
division, you use the mod operator, % .
Applying this discussion to 646 cents yields the following calculations:
1. Change ¼ 646
2. Number of half-dollars ¼ 646 / 50 ¼ 12
3. Remaining change ¼ 646 % 50 ¼ 46
4. Number of quarters ¼ 46 / 25 ¼ 1
5. Remaining change ¼ 46 % 25 ¼ 21
6. Number of dimes ¼ 21 / 10 ¼ 2
7. Remaining change ¼ 21 % 10 ¼ 1
8. Number of nickels ¼ 1 / 5 ¼ 0
9. Number of pennies ¼ remaining change ¼ 1 % 5 ¼ 1

PROBLEM
ANALYSIS
AND
ALGORITHM
DESIGN

This discussion translates into the following algorithm:

1. Get the change in cents.
2. Find the number of half-dollars.
3. Calculate the remaining change.
4. Find the number of quarters.
5. Calculate the remaining change.
6. Find the number of dimes.