Top-Down 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
High-level 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: Put It In 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")