DOC

# Identify algorithm structures

By Mario Arnold,2014-11-26 13:13
10 views 0
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

2 ? State of New South Wales, Department of Education and Training 2006

What is an algorithm?

Lets 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

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 computers 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

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

Output PRINT, DISPLAY, SHOW

Initialise SET, ASSIGN, INIT

Misc FIND, SEARCH, SELECT, SORT

? State of New South Wales, Department of Education and Training 2006 5

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

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

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 exampleSaturday Morning

? State of New South Wales, Department of Education and Training 2006 7

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

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 computers memory. Thankfully, you

dont 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

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

Report this document

For any questions or suggestions please email
cust-service@docsford.com