TopDown Programming Example: Making Change
Step #1: Goal and General Algorithm Idea
Goal: write a program to determine how many quarters, dimes, nickels, and pennies
make up a given amount of change
Specification:
User enters an amount as an integer
Program prints number of quarters, dimes, nickels, and pennies that make up the given amount
Highlevel design:
read in amount
figure out how may quarters are in the amount
determine how much is left over from this
figure out how many dimes are in what’s left over
determine how much is left over from this
figure out how many nickels are in what’s left over
what’s left is the number of pennies
Step #2: Data Representation and Program Structure
Part #1: Data Representation
Represent the amount as an integer
Part #2: Program Structure
 Read in the input
 Divide by 25 to get the number of quarters
 Get the remainder
 Divide by 10 to get the number of dimes
 Get the remainder
 Divide by 5 to get the number of nickels
 Get the remainder
 Print the number of quarters, dimes, nickels, and pennies
Part #3: Refine algorithm
 read in the amount A
 convert A to an integer IA
 divide IA by 25 to get the number of quarters NQ
 take the remainder of IA when divided by 25 to get the new integer IA
 divide IA by 10 to get the number of dimes ND
 take the remainder of IA when divided by 10 to get the new integer IA
 divide IA by 5 to get the number of nickels NN
 take the remainder of IA when divided by 5 to get the new integer IA
 this is the number of pennies NP
 print A "cents is" NQ "quarters," ND "dimes," NN "nickels, and" NP "pennies"
Step #3: Translate This Into Pseudocode
 A ← read("Amount of change: ")
 IA ← int(A)
 NQ ← intdiv(IA, 25)
 IA ← intrem(IA, 25)
 ND ← intdiv(IA, 10)
 IA ← intrem(IA, 10)
 NN ← intdiv(IA, 5)
 IA ← intrem(IA, 5)
 NP ← IA
 print A "cents is" NQ "quarters," ND "dimes," NN "nickels, and" NP "pennies"
Step #4: Translate That Into Python
This is program change0.py.
# read in the amount of change and make it a number
A = input("Amount of change: ")
IA = int(A)
# how many quarters
NQ = IA / 25
# how many dimes in what’s left over
IA = IA % 25
ND = IA /10
# how many nickels in what’s left over
IA = IA % 10
NN = IA / 5
# how many pennies in what’s left over
IA = IA % 5
print A, "cents is", NQ, "quarters,", ND, "dimes,", NN, "nickels, and",\
IA, "pennies"

Matt Bishop
Department of Computer Science
University of California at Davis
Davis, CA 956168562 USA


Last modified: Version of December 31, 2017 at 11:27PM
Winter Quarter 2018
You can get a PDF version of this
