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 make_change.py.

 1. # read in the amount of change and make it a number
 2. A = input("Amount of change: ")
 3. IA = int(A)
 4. # how many quarters
 5. NQ = IA // 25
 6. # how many dimes in what's left over
 7. IA = IA % 25
 8. ND = IA // 10
 9. # how many nickels in what's left over
10. IA = IA % 10
11. NN = IA // 5
12. # how many pennies in what's left over
13. IA = IA % 5
14. print(A, "cents is", NQ, "quarters,", ND, "dimes,", NN, "nickels, and", IA, "pennies")

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: [email protected]

ECS 235A, Computer and Information Security Version of September 28, 2023 at 12:01PM

You can also obtain a PDF version of this.