|
|
Next: Example Two: Using a
Up: Further Structured Design
Previous: Repetition Control Structures
The following algorithm illustrates several techniques. The requirement is for a program which given a set of positive data values will output the minimum value, the maximum value and the average value of the data values.
Before starting on the algorithmic description it must be decided how termination of the data is to be signalled. It would be irritating to the user if after each data entry a yes or no reply had to be given to a question asking whether there was any more data. Equally it might be difficult (and error-prone) for the user to give a count of the number of data elements before processing starts. In this case a better way is to make use of the fact that all the numbers are positive, if the user then enters a negative number when there are no more numbers to process then the program can easily recognise this entry as not being a data entry and hence terminate the entry of data. This technique of placing a sentinel to terminate an input list is commonplace.
It must also be decided what should happen when there is no input, that is the user enters a negative number initially. Also it must be known what type of numbers are entered, are they whole numbers or real numbers? Hence the following improved requirement specification:
A user is to enter positive real values from the keyboard when prompted by the program. To signal end of input the user enters a negative number. When data entry has terminated the program should output the minimum positive value entered, the maximum positive value entered and the average of the positive values entered. If there is no data entry (the user enters a negative number initially) then the program should output a message indicating that no data has been entered.
In this program as each number is entered it must be compared with zero to check if it is the sentinel value that terminates input. Each positive number must be added to an accumulated sum and a count of the number of numbers entered must be incremented (so the average can be found). Also each positive number entered must be compared with the minimum/maximum entered so far and if necessary these values are updated. This means that while the entered number is positive it must be processed. Thus a first attempt at an algorithm might be:
initialise.
enter first value.
while (value is positive)
{
process value.
enter a value.
}
if no data entry
then output `no data entry'
otherwise
{
evaluate average.
output results.
}
As usual the first thing done in this algorithm is an
initialise step. This will be expanded later once the details
of the rest of the algorithm have been finalised. The
process value statement must carry out various tasks.
The sum of the input
data values must be accumulated and a count of the number of values
entered must be incremented. The data value read in must be compared
with the minimum/maximum so far input and if necessary these values
are updated. Hence the expansion of process value is:
process value:
add value to accumulated sum.
add one to count of number of values.
if value is bigger than saved maximum then
put value in saved maximum.
if value is less than saved minimum then
put value in saved minimum.
Looking at this expansion it is obvious that prior to the first entry to the loop the following variables require initialisation:
process value the only previous value is the first value,
hence the initialisation is to set the saved maximum and the saved
minimum to this value.
set sum to zero.
set count to zero.
enter first value.
set saved minimum and saved maximum
to this value.
If no data is entered then this can be recognised by the fact that
count will be zero after execution of the while statement.
Finding the average merely requires dividing the sum by the count of
values and output is fairly obvious. Thus the final version is:
set sum to zero.
set count to zero.
enter first value.
set minimum and maximum to this value.
while (value is positive)
{
add value to sum.
add one to count.
if value is bigger than maximum then
set maximum to value.
if value is smaller than minimum then
set minimum to value.
read a value.
}
if count is zero
then output `no data entry'
else {
set average to sum/count.
output count, average, maximum and minimum.
}
Note that if no data is entered then the terminating negative value will be assigned to minimum and maximum. This does not matter because in this case no use is made of these variables.