Reading: Identify algorithm structures
Identify algorithm structures
Inside this resource What is an algorithm? 3 Features of a good algorithm 3 Expressing algorithms 5 Typical computer operations 8 Accepting inputs 8 Producing outputs 8 Assigning values to variables 9 Performing arithmetic 10 Perform alternative actions 10 Repeating operations 10 Sequence, selection and iteration 11 Structured programming 25 Nesting IF constructs 26 Designing algorithms 28 Algorithm pre-conditions 28 Summary 29 Progress 错误；未定义书签。29
? State of New South Wales, Department of Education and Training 2006 1
Reading: Identify algorithm structures
2 ? State of New South Wales, Department of Education and Training 2006
Reading: Identify algorithm structures
What is an algorithm?
Let’s begin by thinking of an algorithm as a recipe. A recipe defines how to take a set of ingredients, apply a variety of processes to those ingredients (in a prescribed order) to produce a finished product.
A recipe will include instructions on how to prepare the ingredients, which ingredients to mix together into which containers, how to cook the ingredients, at what temperature to cook them, how long to cook them and what to do once they are cooked.
Features of a good algorithm
Algorithms must be precise and unambiguous
This will enable the programmer to code the algorithm into instructions for a computer without having to guess what should be done by the program. An algorithm should describe all of the essential features of the solution. An algorithm is a correct description of the solution to a problem
This statement essentially tells us two things. Firstly, we have a problem. It is vital that we understand the problem before we start describing a solution with our algorithm. There is little value to writing an algorithm that is based on a poorly understood problem. Any program written from that algorithm will fail to solve the problem. Secondly, we must describe the solution correctly with our algorithm. We may be able to arrive at the best possible solution to a problem, but if we fail to represent that solution correctly in our algorithm, any programs written from it will not work as we had planned. There is little point writing code from an algorithm that does not represent the solution correctly.
? State of New South Wales, Department of Education and Training 2006 3
Reading: Identify algorithm structures
Programs should deal gracefully with errors
A program should not ‘die’ or ‘hang’ because of errors such as not finding a
file, or the user entering the letter ‘A’ rather than the number ‘1’. Your
program should include a course of action for all possible situations. For example, if the user tries to open a file which does not exist, a good program might give an error message, and then offer to create a new file. An algorithm might only specify the essential features of a solution, and not the details of error handling. It will then be up to the programmer to enhance the algorithm accordingly.
Useful algorithms are guaranteed to end
Some algorithms may give a solution to a problem in theory, but in practice will fail to produce a solution in a reasonable time. In extreme cases, the algorithm may take an infinite amount of time to produce a result. If we write a program that cannot end (because it was based on an algorithm that did not end) and run that program on our computer, the only way to stop the program would be to terminate the program.
The most common cause of a program not ending is an error (a ‘bug’) in
either the algorithm or the program that produces an infinite loop. There are some special cases where a program is purposely designed not to end, typically where the program is controlling an external device or system (for example a mobile phone, or an aircraft flight-control system).
Algorithms should be efficient
Efficiency can be measured in terms of amount of memory used, the number of operations performed, the frequency of input/output operations and so on. An efficient algorithm will consume less of the computer’s resources than
an inefficient algorithm.
Computer programs should be user friendly
Programs should offer some information and feedback to the operator and should be written with the user in mind. A computer program that is not user friendly will not find many users, and may greatly aggravate those required to use it. Issues include what prompts should be used, window layout, menu design, how information is presented and so on.
4 ? State of New South Wales, Department of Education and Training 2006
Reading: Identify algorithm structures
Expressing algorithms
Described below are three common ways to express the structure of an algorithm:
1 Pseudocode
2 Flowcharts
3 Nassi-Schneidermann diagrams.
Pseudocode
Pseudocode is structured English used for describing algorithms. The purpose of pseudocode is to provide a means of specifying algorithms that is independent of any particular programming language. It allows the program designer to focus on the logic of the algorithm without the distraction of programming language rules.
Pseudocode should be:
; Precise — the writer and all subsequent readers will understand
exactly what is required to be done.
; Concise — pseudocode removes the necessity for verbose, essay-
like instructions containing vague or ambiguous language.
; language independent — the programmer is free to implement an
algorithm in the syntax of any chosen procedural programming
language (the ‘target’ language).
There is a wide variation in pseudocode syntax, but the main thing is that the meaning is readily understood and unambiguous. Organisations that use pseudocode often develop an in-house standard which defines the structure, constructs and keywords that may be used by their designers. Here are some keywords commonly used in pseudocode to indicate input, output, and processing operations:
Pseudocode key word Indicates
Input GET, READ, OBTAIN, ACCEPT
Output PRINT, DISPLAY, SHOW
Initialise SET, ASSIGN, INIT
Add one INCREMENT
Misc FIND, SEARCH, SELECT, SORT
? State of New South Wales, Department of Education and Training 2006 5
Reading: Identify algorithm structures
Here is a simple example of pseudocode that represents what we might do on Saturday morning:
Wake Up
Perform morning things
IF it is raining THEN
Watch TV
ELSE
Play golf
ENDIF
Get ready for lunch
Flowcharts
Flowcharts are a diagrammatic method used to represent processes. The basic symbols used in flowcharts will be introduced as we explore how to represent the three basic algorithmic constructs of sequence, selection and iteration.
Figure 1: Flowchart example: Saturday morning
6 ? State of New South Wales, Department of Education and Training 2006
Reading: Identify algorithm structures
Nassi-Schneiderman diagrams
These diagrams are similar to flowcharts, but have the advantage of
enforcing a particular structure in the program. They can become difficult to
draw when the algorithm includes a lot of nested constructs. We will not be
using Nassi-Schneidermann diagrams.
Figure 2: Nassi-Schneidermann diagram example—Saturday Morning
? State of New South Wales, Department of Education and Training 2006 7
Reading: Identify algorithm structures
Typical computer operations
One way to think about what computers do is the ‘Input-Process-Output’
model. This simple model says that computers perform three basic types of
operations:
1 They take inputs from a variety of different sources.
2 They process these inputs in a variety of ways.
3 They output the results of the processing to a variety of different
devices.
Accepting inputs
Inputs may come from a variety of sources, such as, keystrokes from a
keyboard, a mouse action, a file stored in the computer, sounds from a
microphone and numerous others. An example is shown below, where the
user is prompted for their surname, and the computer reads it into a variable.
English-like statements Example programming instructions
Prompt user for surname surname = raw_input('Enter your Surname')
Input surname
Producing outputs
Outputs may be a file to be stored on disk, information to display on a
screen, information to be printed, sounds to be sent to speakers etc. In the
example below, the text ‘Hello World’ will be sent to the output device (eg
a computer screen).
English-like statements Example programming instructions
Print the message Hello World print 'Hello World'
8 ? State of New South Wales, Department of Education and Training 2006
Reading: Identify algorithm structures
Assigning values to variables
A computer is able to store data values like numbers and text in memory. Programming languages allow you to access memory using named variables. For example, the statement:
x = 6
places the number 6 into a variable called x. The variable x will (when the program executes) be a location in the computer’s memory. Thankfully, you
don’t need to worry about where the number is stored, or how it is represented — you only need to perform processing with the variable. As the name suggests, the actual data stored in a variable may change during the execution of a program or script.
Variables can store numbers or text. The basic data types are numbers and text.
; Numbers can be whole numbers (called integers) such as 2, 27 and
139 or real numbers (numbers that contain an integer and a fraction
shown as one or more decimal places) for example 12.3 and 0.0027.
; Text can be single characters such as ‘A’, ‘g’, ‘Y’ or a string of
characters such as ‘Hello World’.
In the example below, the variable called ‘total’ is set to zero; this is a way
of telling the computer to store the value 0 in the memory location or
variable called total.
English-like statements Example programming instructions
Set the total to 0 total = 0
The name you give to a variable may refer to a storage location that is only one byte in size or a location that is many bytes in size. You should always use meaningful names for variables in algorithms to improve the readability of the algorithm and its resulting program. This is particularly important in large and complex programs.
? State of New South Wales, Department of Education and Training 2006 9
Reading: Identify algorithm structures
Performing arithmetic
Computers can perform the arithmetic operations of adding, multiplying, dividing, subtracting and exponentiation. An example is the following statement which is a way of telling the computer to multiply the number of items and the price, placing the result into the variable called total.
English-like statements Example programming instructions
set total to items times total = items * price
price
Perform alternative actions
Computers can compare the values stored in memory and execute different instructions depending on the result of the comparison. This action is referred to as selection — that is, selecting different courses of action
depending upon some condition. An example is the following statement which is a way of telling the computer to make the decision to print either the word Pass or the word Fail depending on whether the value stored in the variable called mark is greater than 49.
English-like statements Example programming instructions
IF mark is greater than 49 THEN if mark > 49: print Pass print 'Pass' ELSE else: print Fail print 'Fail'
Repeating operations
Computers can execute the same set of instructions over and over again. This is commonly referred to as iteration, repetition or looping. There are several types of iteration that can be used depending on what you want the computer to do. A loop can be constructed to execute the same set of instructions for a certain number of times or to execute the set of instructions while a condition is true. For example, while the total stays above 0 the computer is to continuously subtract the new purchase amount from the total.
10 ? State of New South Wales, Department of Education and Training 2006