DOC

Identify algorithm structures

By Mario Arnold,2014-11-26 13:13
9 views 0
Identify algorithm structures

     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?

    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

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

     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.