Transcript Document

Developing an Algorithm
Objectives
• In this chapter you will be able to:
• Introduce methods of analyzing a problem
and developing a solution
• Develop simple algorithms using the
sequence control structure
• Introduce methods of manually checking the
developed solution
Simple Program Design, Fourth Edition
Chapter 3
2
Defining the Problem
•
To help with this initial
analysis, the problem should
be divided into three
separate components:
1.
Input: a list of the source
data provided to the
problem.
2.
Output: a list of the outputs
required.
3.
Processing: a list of actions
needed to produce the
required outputs.
Input
Simple Program Design, Fourth Edition
Processing
Chapter 3
Output
3
Defining the Problem
•
When dividing a problem into its three different
components, you should simply analyze the
actual words used in the specification, and
divide them into those that are descriptive and
those that imply actions
Simple Program Design, Fourth Edition
Chapter 3
4
Example 3.1 Add Three Numbers
• A program is required to
read three numbers, add
them together and print
their total
• Tackle this problem in two
stages
• First, underline the nouns
and adjectives used in the
specification
• A program is required to
read three numbers, add
them together and print
their total
Input
Processing
Number1
Output
Total
Number2
Number3
Simple Program Design, Fourth Edition
Chapter 3
5
Example 3.1 Add Three Numbers
• Second, underline (in a
different color) the verbs
and adverbs used in the
specification
• A program is required to
read three numbers, add
them together and print
their total
•
•
By looking at the underlined
words, you can see that the
processing verbs are ‘read,’
‘add together,’ and ‘print’
•
Each action is described as a
single verb followed by a twoword object
Input
Processing
Output
Number1
Read three numbers
Total
Number2
Add numbers together
Number3
Print total number
Each action is described as a
single verb followed by a twoword object
Simple Program Design, Fourth Edition
Chapter 3
6
Example 3.2 Find Average
Temperature
• A program is required to prompt the terminal
operator for maximum and minimum temperature
readings on a particular day, accept those
readings as integers, and calculate and display to
the screen the average temperature, calculated
by (maximum temperature – minimum
temperature)/2.
Simple Program Design, Fourth Edition
Chapter 3
7
Example 3.2 Find Average
Temperature
• Establish input and output components
A program is required to prompt the terminal
operator for maximum and minimum temperature
readings on a particular day, accept those
readings as integers, and calculate and display to
the screen the average temperature, calculated
by (maximum temperature – minimum
temperature)/2.
Simple Program Design, Fourth Edition
Chapter 3
8
Example 3.2 Find Average
Temperature
• Establish processing steps
A program is required to prompt the terminal
operator for maximum and minimum temperature
readings on a particular day, accept those
readings as integers, and calculate and display to
the screen the average temperature, calculated
by (maximum temperature – minimum
temperature)/2.
Simple Program Design, Fourth Edition
Chapter 3
9
Example 3.2 Find Average
Temperature
• Defining diagram
Input
Processing
Output
Max_temp
Prompt for temperatures
Avg_temp
Min_temp
Get temperatures
Calculate average temperature
Display average temperature
Simple Program Design, Fourth Edition
Chapter 3
10
Example 3.3 Compute Mowing Time
• A program is required to read from the screen the
length and width of a rectangular house block,
and the length and width of the rectangular house
that has been built on the block. The algorithm
should then compute and display the mowing
time required to cut the grass around the house,
at the rate of two square metres per minute
Simple Program Design, Fourth Edition
Chapter 3
11
Example 3.3 Compute Mowing Time
Input and Out components
• A program is required to read from the screen the
length and width of a rectangular house block,
and the length and width of the rectangular house
that has been built on the block. The algorithm
should then compute and display the mowing
time required to cut the grass around the house,
at the rate of two square metres per minute
Simple Program Design, Fourth Edition
Chapter 3
12
Example 3.3 Compute Mowing Time
Processing steps
• A program is required to read from the screen the
length and width of a rectangular house block,
and the length and width of the rectangular house
that has been built on the block. The algorithm
should then compute and display the mowing
time required to cut the grass around the house,
at the rate of two square metres per minute
Simple Program Design, Fourth Edition
Chapter 3
13
Example 3.3 Compute Mowing Time
Defining diagram
Input
Processing
Output
Block_length
Prompt for block measurements
Mowing_time
Block_width
Get block measurements
House_length
Prompt for house measurements
House_width
Get house measurements
Calculate mowing area
Calculate mowing time
Simple Program Design, Fourth Edition
Chapter 3
14
Designing a Solution Algorithm
• Designing a solution algorithm is the most
challenging task in the life cycle of a program
• Once the problem has been properly defined, you
usually begin with a rough sketch of the steps
required to solve the problem
• The first attempt at designing a particular algorithm
usually does not result in a finished product
• Pseudocode is useful in this trial-and-error process,
since it is relatively easy to add, delete, or alter an
instruction
Simple Program Design, Fourth Edition
Chapter 3
15
Designing a Solution Algorithm
• Solution algorithm for
Example 3.1
Add_three_numbers
Input
Processing
Output
Number1
Read three numbers
Total
Number2
Add numbers
together
Number3
Print total number
Read number1, number2, number3
total = number1 + number2 + number 3
Print total
END
Simple Program Design, Fourth Edition
Chapter 3
16
Designing a Solution Algorithm
• Solution algorithm for
Example 3.3
Calculate_mowing_time
Input
Processing
Output
Max_temp
Prompt for temperatures
Avg_temp
Min_temp
Get temperatures
Prompt operator for block_length, block_width
Calculate average
temperature
Get block_length, block_width
Display average temperature
Prompt operator for house_length, house_width
Get house_length, house_width
house_area = house_length * house_width
mowning_area = block_area – house_area
mowing_time = mowing_area/2
Output mowing_time to screen
END
Simple Program Design, Fourth Edition
Chapter 3
17
Checking the Solution Algorithm
• After a solution algorithm has been established, it
must be tested for correctness
• This step is necessary because most major logic
errors occur during the development of the
algorithm, and if not detected, these errors can be
passed on to the program
• Desk checking involves tracing through the logic
of the algorithm with some chosen test data
Simple Program Design, Fourth Edition
Chapter 3
18
Selecting Test Data
• When selecting test data to desk check an
algorithm, you must look at the program
specification and choose simple test
cases only, based on the requirements of
the specification, not the algorithm
• By doing this, you will still be able to
concentrate on what the program is
supposed to do, not how
Simple Program Design, Fourth Edition
Chapter 3
19
Steps in Desk Checking an Algorithm
• There are six simple steps to follow when desk
checking an algorithm listed on page 26 of the
textbook
• By desk checking an algorithm, you are
attempting to detect early errors
• It is a good idea for someone other than the
author of the solution algorithm to design the test
data for the program, as they are not influenced
by the program logic
Simple Program Design, Fourth Edition
Chapter 3
20
Checking the Solution Algorithm
Desk check Example 3.1
Test data
Add_three_numbers
First dataset
Read number1, number2, number3
total = number1 + number2 +
number 3
Print total
number1
10
40
number2
20
41
number3
30
42
Expected Results
First dataset
END
Second dataset
total
Simple Program Design, Fourth Edition
60
Chapter 3
Second dataset
123
21
Checking the Solution Algorithm
Desk check Example 3.1
Add_three_numbers
Statement #
Read number1, number2, number3
END
number1
number2
number3
total
First pass
total = number1 + number2 + number 3
1
Print total
2
60
3
Print
10
20
30
Second pass
1
40
41
42
2
123
3
Print
Simple Program Design, Fourth Edition
Chapter 3
22
Summary
• The first section of this chapter was devoted to
methods of analyzing and defining a
programming problem
• You must fully understand a problem before you
can attempt to find a solution
• The method suggested was to analyze the actual
words used in the specification with the aim of
dividing the problem into three separate
components: input, output, and processing
Simple Program Design, Fourth Edition
Chapter 3
23
Summary
• The second section was devoted to the
establishment of a solution algorithm
• After the initial analysis of the problem, you
must attempt to find a solution and express
the solution as an algorithm
• The third section was concerned with
checking the algorithm for correctness
Simple Program Design, Fourth Edition
Chapter 3
24
Practice Problems
1. Construct an algorithm that will prompt an operator to
input three characters, receive those three characters, and
display a welcoming message to the screen such as ‘Hello
xxx! We hope you have a nice day’.
•
Answer outline:
–
Define problem by constructing a defining diagram
–
Create a solution algorithm using pseudocode
–
Desk check the solution algorithm using two valid cases
Simple Program Design, Fourth Edition
Chapter 3
25
Practice Problems
3. You require an algorithm that will receive an integer from
the screen, add 5 to it, double it, subtract 7 from it, and
display the final number to the screen.
•
Answer outline:
–
Define problem by constructing a defining diagram
–
Create a solution algorithm using pseudocode
–
Desk check the solution algorithm using two valid cases
Simple Program Design, Fourth Edition
Chapter 3
26