|
|
Next: Statements required to describe
Up: Algorithms
Previous: Algorithms
A simple example is used to look at the problem of designing an algorithm in a suitable form for implementation on a computer. The simple computational problem considered is:
Write a program to input some numbers and output their average.
This is a very informal specification and is not complete enough to define exactly what the program should do. For example where are the numbers going to come from--entered by the user from the keyboard or perhaps read from a file? Obviously to find the average of a series of numbers one adds them together to find their sum and then divides by the number of numbers in the series. So how is the number of numbers entered known? For example it could be input as part of the data of the program or the program could count the numbers as they are entered. This supposes that the program has some way of knowing when the user has stopped entering numbers or when the end of the file has been reached. Another important question is `what should the program do if no data is entered?'. It would then be nonsensical to print out an average value! Keeping these questions in mind leads to the following more specific requirement specification:
Write a program which inputs a series of numbers and outputs their average. The numbers are supplied in a data file and are terminated by an end-of-file marker. In the event that the file is empty a message to that effect should be output.
An algorithm is now required to solve this problem. Obviously the algorithm could be described by `read in the numbers from the file, add them up and divide by the number of numbers to get the average'. In practice this algorithmic description is not sufficiently detailed to describe a computer algorithm. The computer can only carry out simple instructions like `read a number', `add a number to another number', etc. Thus an algorithm must be described in such simple terms. Consider the following first version of a solution:
1 carry out any initialisations required.
2 while not reached end of file do
3 {
4 read in next number.
5 add the number to the accumulated sum.
6 increment the count of numbers input.
7 }
8 evaluate the average.
Note that the line numbers are not required, they are merely for reference. It is commonplace in computer algorithms that certain initialisations have to be carried out before processing begins. Hence as a reminder that this might be necessary a phrase is inserted to indicate that initialisation may be required at the beginning of every algorithm description as in line 1. Once the rest of the algorithm has been developed this initialisation step can be expanded to carry out any initialisations that are necessary.
At line 2 a statement is used which describes a loop. This loop executes the statements contained between the brackets in lines 3-7 continuously as long as the condition `not reached end of file' remains true. The brackets are used to show that the statements in lines 4, 5 and 6 are associated together and are executed as if they were one statement. Without the brackets only statement 4 would be executed each time round the loop. This is not the only repetition statement that may be used, others are possible and will be seen later. In the body of the loop, lines 4-6, each instruction is a simple executable instruction. Once the end of the file is reached then control transfers from the loop to the next instruction after the loop, evaluating the average at line 8. This requires more expansion, since, if there are no numbers input then the average cannot be evaluated. Hence line 8 is expanded to:
8a if no numbers input
8b then print message `no input'
8c otherwise {
8d set average equal to the accumulated sum
8e divided by the number of numbers.
8f print the average.
8g }
Here a conditional statement has been used with the
condition `no numbers input', if this is true then the statement after
the then is executed, while if it is not true the statement after the
otherwise is executed. This process is often called a
`Selection' process.
On studying the above algorithm it is obvious that the process carried out is what a human being might do if given a sheet of paper with many numbers on it and asked to find the average. Thus a person might run their finger down the numbers adding them as they go to an accumulated total until there were no more and then counting the number of numbers and dividing the total by this number to get the average. When this is done it is implicit in their reasoning that the total and the count will both start of at zero before starting to process the numbers. This is not obvious to the computer at all, hence it must be remembered in describing computer algorithms to initialise all sum accumulation variables and counters suitably before commencing processing. Also it must be ensured that processing starts at the beginning of the file. Hence the initialisation (line 1) can be expanded as follows:
1a set accumulated sum to zero. 1b set number count to zero. 1c open file ready to read first data item.
Note that if there were no data items in the file then the first element in the file would be the end-of-file marker. Thus the `while-loop' condition would be false initially so the loop would not be executed and the number of numbers would remain at zero. This would ensure that the condition at line 8a was true hence the appropriate message would be output.
The whole algorithm is now:
set accumulated total to zero.
set number count to zero.
open file ready to read first item.
while not at end of file do
{
read next number from file.
add number to accumulated total.
increment number count.
}
if number count is zero
then print message `no input'
otherwise {
set average to accumulated total divided
by the number count.
print average.
}