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

1. read in the amount A
2. convert A to an integer IA
3. divide IA by 25 to get the number of quarters NQ
4. take the remainder of IA when divided by 25 to get the new integer IA
5. divide IA by 10 to get the number of dimes ND
6. take the remainder of IA when divided by 10 to get the new integer IA
7. divide IA by 5 to get the number of nickels NN
8. take the remainder of IA when divided by 5 to get the new integer IA
9. this is the number of pennies NP
10. print A "cents is" NQ "quarters," ND "dimes," NN "nickels, and" NP "pennies"

Step #3: Translate This Into Pseudocode

1. A ← read("Amount of change: ")
2. IA ← int(A)
3. NQ ← intdiv(IA, 25)
4. IA ← intrem(IA, 25)
5. ND ← intdiv(IA, 10)
6. IA ← intrem(IA, 10)
7. NN ← intdiv(IA, 5)
8. IA ← intrem(IA, 5)
9. NP ← IA
10. print(A "cents is" NQ "quarters," ND "dimes," NN "nickels, and" NP "pennies")

Step #4: Translate That Into Python

This is program change-write.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 95616-8562 USA

Last modified: Version of December 16, 2018 at 3:49PM Winter Quarter 2019 You can get a PDF version of this