The essence of the method has been described above. First, the original problem is analyzed. It has subtasks. A hierarchy of such subtasks is built (Fig. 48).
Then algorithms (or programs) are compiled, starting with the main algorithm (main program), then - auxiliary algorithms (subroutines) with sequential deepening of the level, until we get algorithms consisting of simple commands.
Let us return to the "Interpreter" problem, which was considered in Sec. 3.16. Recall the condition: given the original character string, which has the following form:
In place of a and b are decimal digits; badge
one of the signs of operations is indicated: +, -, *. We need the machine to evaluate this expression and, after the = sign, output the result. The division operation is not considered to deal only with integers.
Let us formulate the requirements for the Interpretator program, which will make it more universal than the version considered in Sec. 3.16:
1. Operands a and b can be multi-valued positive integers within MaxInt.
2. There may be spaces between the elements of the line, as well as at the beginning and at the end.
3. The program performs syntactic control of the text. Let's restrict ourselves to the simplest version of the control: the string should consist only of numbers, operation signs, the = sign and spaces.
4. Semantic control is carried out: the string must be built according to the scheme a
b=. Error if any element is missing or out of order.
5. The range of values of the operands and the result is controlled (should 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 representing the algorithm in its most general form as a linear sequence of steps for solving the problem:
1. Enter a string.
2. Syntactic control (are there any invalid characters?).
3. Semantic control (is the expression correct?).
4. Selection of operands. Checking operands for a valid range of values. Convert to integers.
5. Performing an operation. Checking the result for a valid range.
6. Output of the result.
Stages 2, 3, 4, 5 will be considered as subtasks of the first level, naming them (and future subroutines) respectively Sintax, Semantika, Operand, Calc
In turn, their implementation will require the solution of 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 allowed value (Error). Summarizing everything that has been said in a schematic form, we obtain a certain structure of subtasks. This structure will correspond to a similar structure of program modules (Fig. 49).
First step of detailing. First, we outline all the necessary subroutines, indicating only their headers (specifications). In place of the body of the subprograms, we write explanatory comments (this type of subprogram is called a "stub"). Let's write the main part of the program. And then we will return to the detailed programming of procedures and functions. At the first stage of programming, instead of the body of the subroutine, we describe its purpose in the form of a comment. Having finally combined the texts of the subroutines with the main program, we obtain a working version of the Interpretator program. Now it can be entered into the computer.
Debugging and testing the program. You can never be sure that a written program will be correct in one fell swoop (although this is possible, it becomes less and less likely as the program becomes more complex). The program is brought to the final working state in the process of debugging.
Errors can be “linguistic”, they can be algorithmic. The first type of errors, as a rule, helps to detect the Pascal compiler. These are errors related to violation of the rules of the programming language. They are also called compile-time errors because they are detected at compile time. Algorithmic errors lead to various consequences. First, there may be unfeasible actions. For example, division by zero, the square root of a negative number, an index out of line, etc. These are runtime errors. They lead to the interruption of the program execution. As a rule, there are system software tools that help in finding such errors.
Another situation is when algorithmic errors do not lead to interruption of program execution. The program is executed to the end, some results are obtained, but they are not correct. For the final debugging of the algorithm and analysis of its correctness, testing is carried out. A test is a variant of solving a problem for which the results are known in advance. As a rule, one test variant does not prove the correctness of the program. The programmer must come up with a test system, build a test plan for exhaustive testing of the entire program.
We have already said that A quality program should never crash.
Successful passing of all tests is a necessary condition for the correctness of the program. Note that in this case it is not necessarily sufficient. The more complex the program, the more difficult it is to build a comprehensive test plan. Experience shows that even in "proprietary" programs, errors are found during operation. Therefore, the problem of program testing is a very important and at the same time very complex problem.
End
Each block can contain both a simple command and a complex structure, but must have one entrance and one output.
branching - algorithmic alternative. With this command, which is also called fork, one of two possible actions is selected depending on the condition. After the command is completed, exit to general continuation:
In pseudocode, this command is generally written as follows:
if<условие>
then<действие 1>
otherwise<действие 2>
Actions indicated after service words then and otherwise, can be simple or compound commands. When a branch instruction is executed, only one of the actions is performed: if the condition is met, then action 1 is performed, otherwise, action 2.
The branch command can be used in abbreviated form (correction) when no action is taken if the condition is not met. In pseudocode, the correction is written like this:
if<условие>
then<действие >
Repeat command (loop). Most algorithms contain a series of repeatedly repeated commands. If such commands were written as a compound follow command, then each repeated command would have to be written exactly as many times as it is repeated. But this is a very uneconomical way of recording. Therefore, to designate repeatedly repeated actions, a special construction is used, called cycle.
The compound loop instruction, also called the repeat instruction, contains a condition that is used to determine the number of repetitions. Consider three types of repeat command.
Repeat command with precondition written in pseudocode as follows:
Bye<условие >
repeat<действие>
By action, as before, we mean a simple or compound command. The execution of such a repetition command consists in the fact that the condition is first checked (hence the name - a cycle with a precondition), and if it is met, then the command written after the service word is executed repeat. After that, the condition is checked again. The loop terminates when the condition is no longer met. This requires that the instruction executed in the loop affect the condition.
The repetition instruction with a precondition in the flowchart language looks like this:
 |
Repeat command with postcondition is performed similarly, only the condition is checked after the command is executed, and the command execution is repeated when the condition is not met, i.e. repetition is made before condition (which is why this type of loop is also called a “before” loop). In pseudocode and flowchart language, a loop with a postcondition is written as follows:
repeat
action
before condition
By action, as before, we mean a simple or compound command.
Loop with a parameter (a known number of repetitions)
For parameter:=N1 before N2 make
action
N1, N2 are expressions that define the initial and final values of the cycle parameter, respectively, N3 is the step of changing the cycle parameter.
If N1< N2, то N3 >0.
If N1 > N2, then N3<0.
In theory necessary and sufficient is only the first type of cycle - a cycle with precondition. Any cyclic algorithm can be built using it. This is a more general version of the loop than the loop-to and the loop with a parameter. But, in some cases, the use of a loop-to and a loop with a parameter turns out to be more convenient.
The structural approach requires compliance with the standard in the image of flowcharts of algorithms. You need to draw them as it was done in all the examples given. Each base structure must have one entry and one way out. A non-standard block diagram is poorly readable, the visibility and semantics of the algorithm are lost.
Most often, the algorithm contains combinations of basic commands interconnected. These structures can be connected in two ways: consistent and nested . This situation is similar to that observed in electrical engineering, where any arbitrarily complex electrical circuit can be decomposed into series and parallel connected sections.
If the block that makes up the body of the cycle is itself a cyclic structure, then it means that nested cycles. In turn, the inner loop can have another loop inside it, and so on. In this regard, the concept of nesting depth cycles. Similarly, branches can be nested within each other.
Structured programming is sometimes referred to in the literature as programming without goto. Indeed, with this approach there is no place for an unconditional transition.
The unjustified use of the unconditional jump operator goto in programs deprives it of structure, and hence all the positive properties associated with it: the transparency and reliability of the algorithm. Although this operator is present in all procedural programming languages, however, following a structural approach, its use should be avoided.
The programming languages Pascal and C are called structured programming languages. They have all the necessary control structures for the structural construction of the program. The structuring of the appearance of the program text gives clarity to this construction. The main technique used for this is line shifts, which must obey the following rules:
Constructs of the same nesting level are written at the same vertical level (start from the same position in the line);
The nested construction is written shifted along the line by several positions to the right relative to its external construction.
The structural technique of algorithmization is not only a form of describing an algorithm, but it is also programmer's way of thinking. When creating an algorithm, one should strive to compose it from standard structures.
Another important technological technique of structured programming is decomposition of the problem to be solved into subtasks- splitting the task into simpler parts of the original task from the point of view of programming.
Algorithms for solving such subproblems are called auxiliary algorithms. In this regard, there are two possible ways in the construction of the algorithm:
"top-down" - first, the main algorithm is built, then auxiliary algorithms;
"bottom up" - first, auxiliary algorithms are compiled, and then the main one.
The first approach is also called the method consistent detail , second - assembly method.
Assembly the method involves the accumulation and use of libraries of auxiliary algorithms implemented in programming languages in the form of subroutines, procedures, functions.
At consistent detailing, first the main algorithm is built, and then calls to the auxiliary algorithms of the first level are introduced into it. After that, auxiliary algorithms of the first level are compiled, in which there may be calls to auxiliary algorithms of the second level, etc. The auxiliary algorithms of the lowest level consist only of simple commands.
Method consistent detail used in any construction of complex objects. This is the natural logical sequence of the designer's thinking: gradual deepening into details. It is practically impossible to construct a rather complicated algorithm in another way.
Thus, the technique of step-by-step detailing can be represented as a diagram:
First, the original problem is analyzed. It has subtasks. A hierarchy of such subtasks is built.
Then algorithms (or programs) are compiled, starting with the main algorithm (main program), then - auxiliary algorithms (subroutines) with sequential deepening of the level, until we get algorithms consisting of simple commands.
The technique of sequential detailing allows you to organize the work of a team of programmers on a complex project. For example, the head of the group builds the main algorithm, and instructs his employees to develop auxiliary algorithms and write the corresponding subroutines. The group members only have to agree on the interface (i.e., the relationship) between the developed software modules, and the internal organization of the program is the programmer's own business.
Debugging and testing the program. One can never be sure that the program written will be correct (although this is possible, but with the complexity of the program it becomes less and less likely). The program is brought to the final working state in the process debugging.
Errors can be "linguistic" - syntactic, and algorithmic (logical). The first type of error is usually detected by the compiler of the programming language. These are errors related to violation of the rules of the programming language. They are also called mistakes. compilation time, for they are found out during compilation. The compiler itself in one form or another informs the user about the nature of the error and its place in the program text. Having corrected another error, the user repeats the compilation. This continues until all errors of this level are eliminated.
Algorithmic errors lead to various consequences. First, there may be unfeasible actions. For example, division by zero, square root of a negative number, index out of bounds of the array, etc. These are errors execution time. They lead to the interruption of the program execution. As a rule, there are system software tools that help in finding such errors.
Another situation is when algorithmic errors do not lead to interruption of program execution. The program is executed to the end, some results are obtained, but they are not correct. For the final debugging of the algorithm and analysis of its correctness, testing is carried out.
Test is a variant of solving a problem for which the results are known in advance. As a rule, one test variant does not prove the correctness of the program. The programmer must come up with a test system, build a test plan for exhaustive testing of the entire program.
Quality program in no way should not end emergency.
Tests of the program should demonstrate that with the correct input of the initial data, the correct results will always be obtained, and if there are errors (syntactic, semantic, out of range), the corresponding messages will be received.
Successful passing of all tests is a necessary condition for the correctness of the program. Note that in this case it is not necessarily sufficient. The more complex the program, the more difficult it is to build a comprehensive test plan. Experience shows that even in "proprietary" programs, errors are found during operation. Therefore, the problem of program testing is a very important and at the same time very complex problem.
The essence of the method has been described above. First, the original problem is analyzed. It has subtasks. A hierarchy of such subtasks is built (Fig. 48).
Then algorithms (or programs) are compiled, starting with the main algorithm (main program), then - auxiliary algorithms (subroutines) with sequential deepening of the level, until we get algorithms consisting of simple commands.
Let us return to the "Interpreter" problem, which was considered in Sect. 3.16. Recall the condition: given the original character string, which has the following form:
In place of a and b are decimal digits; badge
one of the signs of operations is indicated: +, -, *. We need the machine to evaluate this expression and, after the = sign, output the result. The division operation is not considered to deal only with integers.
Let us formulate the requirements for the Interpretator program, which will make it more universal than the version considered in Sec. 3.16:
1. Operands a and b can be multi-valued positive integers within MaxInt.
2. There may be spaces between the elements of the line, as well as at the beginning and at the end.
3. The program performs syntactic control of the text. Let's restrict ourselves to the simplest version of the control: the string should consist only of numbers, operation signs, the = sign and spaces.
4. Semantic control is carried out: the string must be built according to the scheme a
b=. Error if any element is missing or out of order.
5. The range of values of the operands and the result is controlled (should 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 representing the algorithm in its most general form as a linear sequence of steps for solving the problem:
1. Enter a string.
2. Syntactic control (are there any invalid characters?).
3. Semantic control (is the expression correct?).
4. Selection of operands. Checking operands for a valid range of values. Convert to integers.
5. Performing an operation. Checking the result for a valid range.
6. Output of the result.
Stages 2, 3, 4, 5 will be considered as subtasks of the first level, naming them (and future subroutines) respectively Sintax, Semantika, Operand, Calc
In turn, their implementation will require the solution of 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 allowed value (Error). Summarizing everything that has been said in a schematic form, we obtain a certain structure of subtasks. This structure will correspond to a similar structure of program modules (Fig. 49).
First step of detailing. First, we outline all the necessary subroutines, indicating only their headers (specifications). In place of the body of the subprograms, we write explanatory comments (this type of subprogram is called a "stub"). Let's write the main part of the program. And then we will return to the detailed programming of procedures and functions. At the first stage of programming, instead of the body of the subroutine, we describe its purpose in the form of a comment. Having finally combined the texts of the subroutines with the main program, we obtain a working version of the Interpretator program. Now it can be entered into the computer.
Debugging and testing the program. You can never be sure that a written program will be correct in one fell swoop (although this is possible, it becomes less and less likely as the program becomes more complex). The program is brought to the final working state in the process of debugging.
Errors can be “linguistic”, they can be algorithmic. The first type of errors, as a rule, helps to detect the Pascal compiler. These are errors related to violation of the rules of the programming language. They are also called compile-time errors because they are detected at compile time. Algorithmic errors lead to various consequences. First, there may be unfeasible actions. For example, division by zero, the square root of a negative number, an index out of line, etc. These are runtime errors. They lead to the interruption of the program execution. As a rule, there are system software tools that help in finding such errors.
Another situation is when algorithmic errors do not lead to interruption of program execution. The program is executed to the end, some results are obtained, but they are not correct. For the final debugging of the algorithm and analysis of its correctness, testing is carried out. A test is a variant of solving a problem for which the results are known in advance. As a rule, one test variant does not prove the correctness of the program. The programmer must come up with a test system, build a test plan for exhaustive testing of the entire program.
We have already said that A quality program should never crash.
Successful passing of all tests is a necessary condition for the correctness of the program. Note that in this case it is not necessarily sufficient. The more complex the program, the more difficult it is to build a comprehensive test plan. Experience shows that even in "proprietary" programs, errors are found during operation. Therefore, the problem of program testing is a very important and at the same time very complex problem.
Lesson type: a lesson in consolidating knowledge and learning new material.
Type of lesson: combined lesson (lecture and practice).Lesson Objectives: General education:
to form an idea among students about the basic concepts of the topic: a branching command, an incomplete form of a branching command;
to form the skills of developing algorithms with branching in the GRIS "Strelochka";
Developing:
development of information vision of the phenomena and processes of the surrounding world;
Educational:
education of information culture of students, attentiveness, accuracy, discipline, perseverance;
education of cognitive interest of schoolchildren
Lesson structure:
I .Organizational moment (2 min.)
Greetings. Checking those present. The topic of the lesson.
II
Written survey 2 work options
III
Explaining with a presentation
An example of a problem with two step details
Explanation with the help of the presentation “Demonstration of the algorithm with branching “Ornament” in the environment of the Strelochka performer”.
IV
V . Summary of the lesson (2 min.)
VI . Homework (1 min.)
During the classes:
I .Organizing time
Lesson topic: “ Branching and progressive drill down ”
The main topics of the paragraph:
♦ branch command;
♦ incomplete form of branching;
♦ an example of a problem with two step details.(slide 2)
II . Updating knowledge (5 min.)
Subject Test:Cyclic algorithms
Option 1
1. In which of the figures the condition is checked:
2. The cyclic algorithm is:
nc
step
kts
until the end is ahead, repeat
nc
step
turn
kts
early
step
con
nc
step
kts
4. The body of the cycle is:
graphical way of describing the algorithm
this is a set of instructions describing the procedure for the performer to achieve the result of solving the problem in a finite number of actions.
an algorithm in which some sequence of commands must be executed several times.
5.Draw the cycle structure (flowchart)
Subject Test:Cyclic algorithms
Option 2
1. In which of the figures the procedure is performed:
2. The cycle is:
an algorithm in which some sequence of commands must be executed several times.
graphical way of describing the algorithm
this is such an algorithmic structure in which repeated repetition of one (or several) commands is carried out.
this is a set of instructions describing the procedure for the performer to achieve the result of solving the problem in a finite number of actions.
3. It is required to draw a horizontal line across the entire screen. Choose the right program:
early
step
con
nc
step
kts
nc
step
turn
kts
until the end is ahead, repeat
nc
step
kts
4. Block diagram is:
a sequence of commands included in the algorithmic structure "cycle".
graphical way of describing the algorithm
this is a set of instructions describing the procedure for the performer to achieve the result of solving the problem in a finite number of actions.
an algorithm in which some sequence of commands must be executed several times.
5. Write a program looping the algorithm.
III . Theoretical part (20 min.)
Branch command
Let's get acquainted with another GRIS team. It is called the branch command. The format of the branch command is:
if<условие>
then<серия 1>
otherwise<серия 2>
sq.(slide 3)
The service word kv denotes the end of a branch.
As before, the GRIS can only check two conditions: “is there an edge ahead?” or “there is no end ahead?”.<Серия>is one or more consecutive commands. If a<условие>is true, then<серия 1>, otherwise -<серия 2>. An example is shown in fig. 5.12.
(slide 4)
Such branching is called complete.
Incomplete form of branching
In some cases, an incomplete form of the branch command is used (Figure 5.13). For example:
if the edge is ahead
then turn
sq.
(slide 4)
An incomplete branch command has the following format:
if<условие>
then<серия>
sq.
Here<серия>is performed if<условие>fair.slide 5)
Let's compose the last, relatively complex program for the GRIS. In this example, you will see that the use of the method of progressive detail makes it easier to solve some "puzzle" problems.
An example of a problem with two-step detailing
Task 6. Construct an ornament consisting of squares located along the edge of the field. The initial position of the HRIS is in the upper left corner, direction to the south (Fig. 5.14).
(slide 6)
Let's call the procedure that draws a chain of squares from edge to edge of the field a ROW. The procedure that draws one square is called SQUARE. Let's write the main program first.
Ornament program
early
make a ROW
turn
make a ROW
turn
make a ROW
turn
make a ROW
con(slide 7)
Now let's write the procedures SERIES and SQUARE:
(slide 8)
In the SERIES procedure, the cycle body contains an incomplete branch. The structure of such an algorithm can be called as follows: a loop with nested branching.
On fig. 5.15 shows a block diagram of the RAD procedure.
Compiling this program required two steps to refine the algorithm, which were performed in the following sequence:
Now you know all the commands for controlling the graphical executor. They can be divided into three groups: simple commands; procedure call command; structural commands. The third group includes loop and branch commands.
(slide 9)
IV . Consolidation of knowledge (15 min.)
Development of the "Ornament" algorithm
V . Summary of the lesson (2 min.)
Evaluation of student work in class.
VI . Homework (1 min.)
§31, questions. Getting ready for the test(slide 10)
Questions and tasks
1. What is drill down?
2. What commands can the auxiliary algorithms of the last level of detail consist of?
3. What is the format of the branch command? What actions of the performer does it define?
4. What is the difference between full branching and incomplete branching?
5. By step-by-step detailing, compose graphics executor control programs to solve the following tasks:
draw the entire field with horizontal dotted lines;
draw squares in all four corners of the field;
draw the entire field in a cell with a side equal to the step.
>>Computer Science: Branching and Sequential Detailing of the Algorithm
§ 31. Branching and sequential detailingalgorithm
The main topics of the paragraph:
♦ branch command;
♦ incomplete form of branching;
♦ an example of a problem with a two-step specification.
Branch command
Let's get acquainted with another GRIS team. It is called the branch command. The format of the branch command is:
if<условие>
then<серия 1>
otherwise<серия 2>
sq.
The service word kv denotes the end of a branch.
As before, the GRIS can only check two conditions: “is there an edge ahead?” or “there is no end ahead?”.<Серия>is one or more consecutive commands. If a<условие>is true, then<серия 1>, otherwise -<серия 2>. An example is shown in fig. 5.12.
Such branching is called complete.
Incomplete form of branching
if the edge is ahead
then turn
sq.
if<условие>
then<серия>
sq.
Here<серия>is performed if<условие>fair.
Let us compose the last, relatively complex program for GRIS. In this example, you will see that the use of the method of progressive detail makes it easier to solve some "puzzle" problems.
An example of a problem with two-step detailing
Task 6. Construct an ornament consisting of squares located along the edge of the field. The initial position of the HRIS is in the upper left corner, direction to the south (Fig. 5.14).
Let's call the procedure that draws a chain of squares from edge to edge of the field a ROW. The procedure that draws one square is called SQUARE. First, write the main program
Ornament program
early
make a ROW
turn
make a ROW
turn
make a ROW
turn
make a ROW
con
Now let's write the procedures SERIES and SQUARE:
In the SERIES procedure, the cycle body contains an incomplete branch. The structure of such an algorithm can be called as follows: a loop with nested branching.
On fig. 5.15 is given block diagram RAD procedures.
Compiling this program required two steps to refine the algorithm, which were performed in the following sequence:
Now you know all the commands for controlling the graphical executor. They can be divided into three groups: simple commands; procedure call command; structural commands. The third group includes loop and branch commands.
Briefly about the main
The branch command has the following format:
if<условие>
then<серия 1>
otherwise<серия 2>
sq.
If a<условие>true, then the commands that make up<серию 1>if false, then -<серию 2>.
An incomplete branch command has the following format:
if<условие>
then<серия>
sq.
If the condition is true, then<серия>, if false, then immediately go to the next command of the algorithm.
Complex algorithms are conveniently built by step-by-step detailing.
Questions and tasks
1. What is drill down?
2. What commands can the auxiliary algorithms of the last level of detail consist of?
3. What is the format of the branch command? What actions of the performer does it define?
4. What is the difference between full branching and incomplete branching?
5. By step-by-step detailing, compose graphics executor control programs to solve the following tasks:
draw the entire field with horizontal dotted lines;
draw squares in all four corners of the field;
draw the entire field in a cell with a side equal to the step.
What You Should Learn from Chapter 5
To master the program control of one of the educational graphic performers.
Write linear programs.
Write cyclical programs.
Write programs that contain branches.
Describe and use auxiliary algorithms (subroutines).
Apply the method of sequential detailing.
I. Semakin, L. Zalogova, S. Rusakov, L. Shestakova, Informatics, Grade 9
Submitted by readers from Internet sites
All computer science online, list of topics by subject, collection of computer science abstracts, homework, questions and answers, computer science abstracts Grade 9, lesson plans
Lesson content lesson summary support frame lesson presentation accelerative methods interactive technologies Practice tasks and exercises self-examination workshops, trainings, cases, quests homework discussion questions rhetorical questions from students Illustrations audio, video clips and multimedia photographs, pictures graphics, tables, schemes humor, anecdotes, jokes, comics parables, sayings, crossword puzzles, quotes Add-ons abstracts articles chips for inquisitive cheat sheets textbooks basic and additional glossary of terms other Improving textbooks and lessonscorrecting errors in the textbook updating a fragment in the textbook elements of innovation in the lesson replacing obsolete knowledge with new ones Only for teachers perfect lessons calendar plan for the year methodological recommendations of the discussion program Integrated LessonsIf you have corrections or suggestions for this lesson,
