Development of a computer science lesson on the topic "Auxiliary algorithms. Method of sequential detailing and assembly method." Branching and sequential refinement of the algorithm

Sequential detailing method.

Computer Science 11th grade

Municipal educational institution "School-lyceum No. 1"

Alushta

Teacher: Litvinovich V.P.

The sequential detailing method is one of the main methods of structured programming.

The essence of this method is to develop complex algorithms by building a hierarchy

subtasks

The essence of the method:

• Analyzed original problem.
• Subtasks are highlighted.
• A hierarchy of subtasks is being built
• An algorithm (program) for the main task is compiled
• An auxiliary algorithm (subroutines) is compiled with a sequential deepening of the level.

Example 1 Calculate the area of ​​a convex N-gon given by the coordinates of its vertices.

Find the area of ​​a convex polygon:

Area of ​​a polygon

is defined as the amount

areas N-2 triangles.

S- triangle is defined:

according to Heron's formula

S =√(p(p-a)(p-b)(p-c)

First step of detailing The sides of a triangle are determined by the Pythagorean theorem: The initial data, the coordinates of the vertices of the triangle, can be specified using an array:

Data organization

Second detail step: Let's program the procedure Treugolnik. In the subroutine section of this procedure we will write only the interface of the subroutine Line, creating a function.

Third step of detailing Let's program the function Line. The coordinates of the ends of the segment are specified by the following parameters: x a, Y a – first point, x b, U b – second.

We collect all the steps taken and create a program:

………………………………………………………………………………………… ..

Application of the sequential detailing method

• Several specialists are working on a large software project.
• The group leader designs the multi-level structure of the algorithm and compiles the main program, and assigns the writing of subroutines to other programmers.
• Programmers need to agree on the interface of subroutines: names, parameters.
• The internal structure of a subroutine is the work of a programmer
• Large subroutine projects are combined into MODULES.

Homework. § 2.2.11 read. Remember …

Practical work № 6. Check the program's operation N ugolnik

Set N = 4

Calculate the area of ​​a square with equal side lengths 2 and vertex coordinates:

Get the result.

The essence of the method was described above. First, the original problem is analyzed. It identifies subtasks. A hierarchy of such subtasks is constructed (Fig. 48).
Then algorithms (or programs) are compiled, starting with the main algorithm (main program), then auxiliary algorithms (subroutines) with successive deepening of the level until we get algorithms consisting of simple commands.Let's return to the “Interpreter” task, which was considered in section. 3.16. Let us recall the condition: given the original character string having next view:A
b=A and b are replaced by decimal digits; icon
one of the operation signs is indicated: +, -, *. We need the machine to evaluate this expression and, after the = sign, display the result. The division operation is not considered in order to deal only with integers. Let us formulate requirements for the Interpretator program that will make it more universal than the option discussed in Section. 3.16:1. Operands a and b can be multi-valued positive integers within MaxInt.2. There may be spaces between line elements, as well as at the beginning and end.3. The program performs syntactic control of the text. Let's limit ourselves to the simplest control option: the line should consist only of numbers, operation signs, the = sign and spaces.4. Semantic control is carried out: the line must be constructed according to scheme a
b =. Error if some element is missing or their order is out of order.5. The range of operand values ​​and the result is controlled (they must not go beyond MaxInt). Already from the list of requirements it becomes clear that the program will not be easy. We will compose it using the method of sequential detailing. Let's start by introducing in the very general view algorithm as a linear sequence of stages for solving a problem: 1. Entering a line.2. Syntactic control (are there any illegal characters?).3. Semantic control (is the expression constructed correctly?).4. Operand selection. Checking operands for a valid range of values. Convert to integers.5. Performing an operation. Checking the result for acceptable range.6. Output of the result. We will consider stages 2, 3, 4, 5 as subtasks of the first level, naming them (and future subroutines) Sintax, Semantika, Operand, Calc accordingly

“Execution of algorithms by a computer” - Formal executor Algorithm and program Features of program execution. What are the features of executing a program in NML on a computer? Basic questions: Ski. Features of executing a computer program written in LPW? broadcast from YAPVU to YAMK. Stages of program execution. Output device. Computer.

“Algorithms in Computer Science” - Action N. I wish you success in studying COMPUTER SCIENCE. Branching algorithm. Output of the result. Entering initial data. Understood the topic well and did a good job in the lesson. Which algorithm is called linear? Indication of the beginning and end of the algorithm. Types of algorithms. Types of algorithms. A lot of work needs to be done on this topic.

“Properties and types of algorithms” - A cyclic algorithmic design in which the condition is set at the beginning of the cycle. The beginning, the end of the algorithm. Types of algorithms. Graphic method descriptions of the algorithm (block diagram). The action being performed. Sequence of actions. Linear algorithm. Incomplete form of a branched algorithm.

“Action algorithms” - How should the algorithm be described? To complete a task, you first think through a sequence of actions. When translated into Latin, the author's name was written as follows: Algorithmi [algorithms]. Light the gas. Algorithms in our lives. Any algorithm can be depicted graphically or described in words. Where does the word "algorithm" come from?

“Informatics “Concept of an algorithm”” - The final sequence of steps. Great amount tasks of varying complexity. Algorithm. Material for the curious. Can a computer solve a problem on its own? How can a computer be used? What is an algorithm? Stages of work. Only humans can develop algorithms. Stepmother. Practical task.

“Algorithm and its formal execution” - Recording the algorithm in the form of a block diagram. Let's take text as an object. Development of programming languages. Coding. Algorithms consist of individual commands. The algorithm should be clear. Basics of algorithmization. Publication or transfer of the work result to the customer. Recording the algorithm. Top-down design.

There are 31 presentations in total

During subsequent detailing, the main algorithm is first constructed, and then calls to auxiliary algorithms of the first level are added to it. After this, auxiliary algorithms of the first level are in place, which may contain calls to auxiliary algorithms of the second level, etc. Auxiliary algorithms lower level consist only of simple commands. The method of sequential detailing will be used in any design complex objects. This is a natural logical consequence of a designer’s thinking: gradual delving into details. The technique of final detailing allows you to organize the work of a team of programs on a complex project. First, the original problem is analyzed. It identifies subtasks. A hierarchy of such subtasks is constructed.

Then the algorithms (or programs) are built, starting with the main algorithm (main program), then auxiliary algorithms (subroutines) with the last deepening of the Level until we get algorithms consisting of simple commands. Task. Condition: the original is given character string, having the following form: a Å b = In place of a and b there are decimal digits; The symbol Å indicates one of the operation signs: *, -, *. It is necessary for the machine to calculate this expression and, after the = sign, display the result. Operands a and b can be multi-valued positive integers within MaxInt. There are spaces between the elements of the line, as well as at the beginning and end. The program carries out syntactic control of the text. Let's limit ourselves to the simplest control option: the line should consist only of numbers, operation signs, the = sign and a space. Semantic control is carried out: the line must be constructed according to the scheme a Å b = . Error if some element is missing or their order is out of order. The range of values ​​of the operands and the result is controlled (they must not go beyond Maxint). Already from the list of requirements it becomes clear that the program will not be easy. We will compose it using the final detailing method. Let's start by presenting the algorithm in its most general form as a linear sequence of stages in solving a problem: Entering a string. Syntactic control (are there any illegal characters?). Semantic control (is the expression constructed correctly?). Operand selection. Checking the operands for the valid range of values. Convert to integers. Number of operations. Checking the result for the acceptable range. Conclusion of the result. We will consider stages 2, 3, 4, 5 as subtasks of the first level, calling them (and future subroutines) Sintax, Semantika, Operand, Calc, respectively. In turn, their implementation will require solving the following subtasks: skipping extra spaces (propusk), converting a character digit to an integer (cifra). In addition, when allocating operands, you will need to recognize an operand that exceeds the maximum permissible value(Error). First step of detailing. First, we outline all the necessary subroutines, indicating only their headings (specifications). In place of the body of the subroutines, we will write explanatory comments. Let's write the main part of the program. And then we'll go back to detailed program procedures and f. Second step of detailing. The condition is poor. Having finally combined the texts of the subroutines with the main program, we obtain a working version of the program Interpolator.

Basic algorithmic structures: following, branching, loop; image on block diagrams. Breaking a task into subtasks. Auxiliary algorithms.

Main types of algorithms (algorithmic structures):

1. Linear algorithm (also called following);

2. Cyclic algorithm;

3. Branching algorithm;

4. Auxiliary algorithm.

Linear algorithm

Linear algorithm – description of actions that are performed once in a given order. The performer performs actions sequentially, one after another in the order in which they occur.

Block diagram linear algorithm:

Round robin algorithm

Best quality computers manifest themselves not when they calculate the meaning of complex expressions, but when they repeat relatively simple operations many times, with minor changes. Even very simple calculations can baffle a person if they need to be repeated thousands of times, and a person is completely incapable of repeating operations millions of times.

Programmers are constantly faced with the need for repetitive calculations. For example, if you need to count how many times the letter “o” appears in the text, you need to go through all the letters. Despite the simplicity of this program, it is very difficult for a person to execute it, but for a computer it is a task that takes a few seconds.

Round robin algorithm– a description of actions that must be repeated a specified number of times or until a specified condition is met.

The list of repeated actions is called body of the loop.

There are two types of cyclic algorithms:

• Loops with a counter, in which some actions are performed a certain number of times;
• Loops with condition in which the body of the loop is executed depending on some condition. There are cycles with precondition and postcondition.

Loops with a counter are used when it is known in advance how many repetitions of the loop body must be performed. For example, in a physical education lesson you have to run a number of laps around the stadium.

IN general case The circuit diagram of the cyclic algorithm with a counter will look like this:

For counter from start values ​​to end valuesexecute action.

It often happens that it is necessary to repeat the body of a loop, but it is not known in advance how many times this should be done. In such cases, the number of repetitions depends on some condition. Such loops are called conditional loops. Loops in which a condition is first checked, and then possibly the body of the loop is executed, are called loops with a precondition. If the condition is checked after the first execution of the loop body, then the loops are called loops with a postcondition.

For example, on Saturday evening you watch TV. From time to time you look at your watch and if the time is less than midnight, then you continue to watch TV; if it is not, then you stop watching TV shows.

In general, the scheme of a cyclic algorithm with a condition will look like this:

Bye conditionrepeat action.

When compiling cyclic algorithms It is important to think about the cycle being finite. A situation in which a loop never ends is called looping.

Branching algorithm

In many cases, it is required that one sequence of actions be performed under certain conditions, and another under other conditions.

If it rains, you need to open an umbrella.

If the alarm clock rings, then you need to get up.

Branching algorithm- an algorithm in which, depending on the condition, either one or another sequence of actions is performed.

These sentences begin with checking some condition: it started to rain, the alarm clock rang, I met Sasha... Then, depending on the situation, we either eliminate some action or do not perform it (or perform some other action).

The computer, too, depending on some condition, can perform or not perform certain actions. The algorithm in which the condition is used is called branching, since depending on the value of the condition, certain actions are selected.

In general, the diagram of a branching algorithm will look like this: “ If condition, That action 1, otherwise action 2» ( If I meet Sasha, I’ll tell him..., otherwise I’ll go see him myself.). You can also use the incomplete form: “ If condition, That action» ( If I meet Sasha, I’ll tell him...). In this case, no action is provided in case of non-fulfillment of the condition.

A condition is a statement that can be either true or false.

Let us note once again that there are two forms of branching - incomplete (when there is only one branch, i.e., depending on the truth of the condition, either the action is performed or not) and complete (when there are two branches, i.e., depending on from the truth of the condition, either one or the other action is performed).

Auxiliary algorithm

Auxiliary algorithm– an algorithm that can be used in other algorithms by specifying only its name.

An auxiliary algorithm written in a programming language is called a subroutine. When creating medium-sized programs, use structured programming, the idea of ​​which is that the structure of the program should reflect the structure of the problem being solved, so that the solution algorithm is clearly visible from source text. The program is divided into many subroutines, each of which performs some action specified in the original task.

By combining subroutines, it is possible to form a final algorithm using blocks of code (subroutines) that have a certain semantic meaning. You can refer to these subroutines by their name. Very important characteristic subroutines are the ability to reuse them.

Let's look at an example with graphic artist GRIS. Let's say we need to create an algorithm for drawing the four-digit number 1919.

You can create one long algorithm according to which the performer will draw these numbers step by step. But the numbers 1 and 9 are repeated twice. The algorithm can be shortened using an auxiliary algorithm.

The result is a shorter and more understandable algorithm:

Algorithm Number "1919"
Start
make UNIT
bounce
make NINE
bounce
make UNIT
bounce
make NINE
end

Where are UNIT and NINE auxiliary algorithms:

Sequential detailing method

The approach we used makes programming easier complex tasks. The task is broken down into simpler subtasks. The solution to each is presented in the form of an auxiliary algorithm, and the main algorithm organizes the connection between them.

A programming method in which the main program is first written, calls to as yet uncomposed subroutines are written in it, and then these subroutines are described is called method of sequential (step-by-step) detailing. Moreover, the number of detail steps can be much greater than in our example, since the subroutines themselves can contain calls to other subroutines.

Assembly method

Another approach to constructing is possible complex programs: Initially, many subroutines are compiled that may be needed to solve the problem, and then the main program is written containing calls to them. Subroutines can be combined into a subroutine library and stored in long-term memory computer. Such a library can be gradually replenished with new subroutines.

For example, if you create a library of procedures for drawing all letters and numbers to control a graphic artist, then the program for obtaining any text will consist of commands for accessing library procedures.

The described method is called assembly programming.

Often in the programming literature the following terminology is used: the sequential granularity method is called top down programming, and the assembly method is p programming from bottom to top.