Drawing up and implementation of algorithms with branching and repetition. Algorithmic structure cycle. Repeat commands Algorithm with repetition

Back forward

Attention! Slide previews are for informational purposes only and may not represent all the features of the presentation. If you are interested this work, please download the full version.

Back forward

Back forward

The lesson “Algorithms with repetition” continues to introduce sixth-graders to basic algorithmic structures. To connect with the previous topic - “branching”, and in order to check the assimilation of key concepts of the topic at the beginning of the lesson, students perform an interactive test individually on computers, depending on their number. The test was created according to the template of A. N. Komarovsky, contains 5 tasks, immediately gives a grade ( Presentation 2 ). The purpose of the test is to check the degree of mastery of the material at a conceptual level in a short period of time. At this time, the rest of the students, using an interactive slide, discuss how to correctly arrange the commands of the “test of divisibility by 3” algorithm in the flowchart, having the opportunity to see the correct arrangement of commands and keywords on another slide. When creating a slide, macros were used that allow moving objects (labels) to a specified area in slide show mode. Macros were proposed by David M. Marcovitz, optimized by A.N. Komarovsky.

The introduction to the new algorithmic design is based on the example of the “fill a barrel” problem. When creating slides illustrating the solution to a problem, special attention is paid to highlighting a repeating action, which is ultimately recorded once, and when the problem is solved again, it is repeated several times.

After demonstrating the general form of the “repetition” construction, consolidation proceeds on the task from workbook"Masha and jam." A blank block diagram is also placed on the slide, and it is filled by moving the inscriptions using the above macros. After discussion and correct placement commands on the slide, students are asked to do the same on their own in the workbook.

To summarize the lesson and reflect, we use the interactive test “Algorithms with repetition”, which also consists of 5 tasks on key concepts of the topic, and immediately gives a grade ( Presentation 3 ). Students are assessed based on their work on tests and their contributions to discussions and assignments. The transition from one stage of the lesson to another and from slide to slide is carried out through control buttons. Work with tasks on slides can be organized both with and without an interactive whiteboard.

Goals:

• develop students' understanding of different forms of algorithms;
• form an idea of ​​algorithms with repetition.

Tasks:

• repeat information about branching algorithms;
• teach to isolate conditions and actions from a repetition task;
• teach how to repeat algorithms.

Lesson type: a lesson in learning and consolidating new knowledge

Equipment: computer class, projector, screen

TsOR: Presentation 1 “Algorithms with repetition”, interactive tests: “Algorithms with branching” ( Presentation 2 ), “Algorithms with repetition” ( Presentation 3 ). All presentations contain macros for proper operation all macros must be enabled .

DURING THE CLASSES

№ p/p	Lesson steps	Contents of the stage	Purpose of the stage	Form of work		Student activities	Resources
1.	Lesson topic, lesson plan (3 min)	Determining the topic of the lesson - solving a rebus (Repetition)	Activate the mental activity of students, repeat methods of encoding information	Frontal work with a slide		They remember ways to encode information in puzzles.	Presentation 1 , slides 1-3:
2.	Repetition, checking homework (5 min)	Repetition of material from the previous lesson, checking homework, task No. 34	Reviewing the basic concepts of branching algorithms, checking homework	Individual work with an interactive test on computers with obtaining a grade, frontal work with the slide “Divisibility by 3”		Performing the test “Algorithms with branching” on computers for evaluation (by the number of computers), the rest - restoring the correct order of commands in the block diagram of the algorithm “Divisibility Test by 3”	Test “Algorithms with branching”, (Presentation 2 ); Flowchart “Divisibility test by 3”: Presentation 1 , slide 4,
Problem #34: Present in the form of a block diagram the sign of divisibility of a natural number by 3. Slide 4 of the presentation (Fig. 1) allows you to do this interactively. To move an inscription in display mode, you need to left-click on the inscription (release the button), then left-click on the area where you intend to move the inscription. If you move by mistake, do the same to correct the error. Slide 5 allows you to check whether the task was completed correctly. Picture 1
3.	Learning new material (15 min)	Analysis of the “Fill a Barrel” problem as an example of an algorithm where the same action is repeated several times, familiarization with the general form of the Repetition structure	Demonstrate an algorithm with repetition as a form of organizing algorithms that allows identical actions to be recorded once and performed as many times as needed.	Collaboration with slides		Discussing the commands needed to solve a problem, highlighting repetitive actions. Writing down a flowchart and repetition commands with keywords in a notebook	Presentation 1 , Slides 7-18
Solving the problem “Fill a barrel” is first demonstrated in the form of a linear algorithm by listing all the commands leading to the solution of the problem ( Presentation 1 , slides 6-9). Then the solution to the same problem is formalized in the form of an algorithm with repetition (Fig. 2), highlighting important points: check condition, execute command, return to condition, exit repetition ( Presentation 1 , slides 10-14). Using slides 15-17, students become familiar with new concepts: a cycle, a general view of the structure, repetition in the form of a flowchart and in algorithmic language. Figure 2
4.	Consolidating new material (10 min)	Solution of the problem “Masha and jam”, problem No. 46.	Teach how to analyze a problem, highlighting the conditions, actions necessary to solve it, and arranging commands in the right order	Group work, independent work with a workbook		Discuss in groups, offer options for solving the problem, participate in arranging teams on the slide, solve the problem independently in workbooks	, Presentation 1 , Slides 18-19.
Problem No. 46. One day, grandma asked Masha to help pick gooseberries. The girl took the basket and approached a large thorny bush. She carefully picked the berry and put it in the basket. Masha did this until there was not a single berry left on the bush. A very tasty jam was made from these berries. Questions and tasks for the task ( Presentation 1 , slide 18 (Fig. 3)): – select from the suggested inscriptions those actions that Masha will have to repeat several times. – what inscription can serve as a condition? – in what order should the labels be placed on the flowchart? (one of the students can rearrange the inscriptions) – will the problem be solved if “yes” and “no” are swapped? Using slide 19, you can check the correct placement of commands on the diagram. Figure 3
5.	Consolidation of new material, testing of knowledge. (5 minutes)	Interactive test “Algorithms with repetition”	Check the degree of mastery of the material on the topic “Algorithms with repetition”	Individual work with the test on computers.		Performing interactive test tasks on computers “Algorithms with repetition”, correcting errors	Test “Algorithms with repetition”, Presentation 3
6.	Lesson summary. (2 minutes)	Grades for tests, frontal and group work.	Summing up, reflection, understanding of the work done	Front work		Getting grades, answering questions
7.	Homework	, clause 3.4, , № 45		Individual work with a textbook, workbook	Reading a textbook, doing exercises		,

Bibliography:

1. Bosova L.L. Computer science: textbook for 6th grade - M.: BINOM. Knowledge Laboratory, 2006.
2. Bosova L.L. Computer Science: Workbook for 6th grade - M.: BINOM. Knowledge Laboratory, 2004.

Lesson plan for 8th grade

Topic: Design and implementation of algorithms with branching and repetition.

Learning Objectives:

Reinforcement of material from previous lessons;

Formation of skills in composing algorithms with branching and repetition;

Development of logical and algorithmic thinking;

Lesson type: lesson to consolidate knowledge, skills and abilities.

Students should know: branch and repetition operators.

Students should be able to: implement and compose programs using branch and repetition operators.

Lesson software and methodological support: system Pascal programming ABC, tutorial"Computer science. 8th grade", §4.

1. Updating knowledge and motivating students to study educational material (frontal form of work). Solving problems with students:

Task 1.

var a,f,s: real;

writeln("Enter the traction force (n): ");

writeln("Enter distance (m): ");

writeln("Perfect work of traction force ",a:5:2," J");

Task 2.

writeln("Enter number: ");

if k=0 then begin

writeln("Square root of the number: ",k1:5:2);

writeln("Reverse number: ",k1:9:6);

2. Drawing up and implementation of algorithms (Explanatory and illustrative teaching method in combination with a partial search method, frontal and individual forms of work).

Task 1.

var m,n,o,min: byte;
(for height value (in cm) 1 byte of memory is enough)

(in this case, height can take values ​​from 0 to 255)

writeln("Enter the height of the three girlfriends (cm)");

write("Masha: "); readln(m);

write("Natasha: "); readln(n);

write("Olya: "); readln(o);

min:= m; (the smallest is Masha)

if o min then min:=o; (the smallest is Olya)

write("The smallest of the girlfriends is ");

if min = m then writeln("Masha")

else if min = n then writeln("Natasha")

else writeln("Olya");

Task 2.

var a,b,c: real;

writeln("Inequality of the form ax

write("a= "); readln(a);

write("b= "); readln(b);

write("x"); (begin derivation of the solution)

(when dividing an inequality by a negative number, the sign of the inequality changes)

if a 0 then write(" print the inequality sign)

else write(" ");

writeln(c:5:2); (we complete the conclusion of the solution)

if (a = 0) and (b 0) then writeln("Any number is a solution to an inequality");

if (a = 0) and (b

Task 3.

var i,k,b,sum,sball_c: integer; (1 byte of memory is enough for the values ​​of these variables)

writeln("Enter the number of students in the group: ");

writeln("Enter your computer science grades for the quarter");

for i:= 1 to k do

writeln("Average score of the group for the quarter: ",sball:5:2);

Task 4.

program cycl_if_1;

var i,k,b,sum,sball_c: byte; (1 byte of memory is enough for variable values)

(in this case they can take values ​​from 0 to 255)

write("Enter the number of marks: ");

for i:= 1 to k do

sum:= sum+b; (sum of marks)

sball:= sum/k; (average score)

writeln("Your average score: ",sball:5:2);

sball_c:= round(sball); (round the average score to whole numbers)

writeln("Round: ",sball_c);

if sball_c = 8 then writeln("Well done!");

if (sball_c = 6) and(sball_c Not bad");

if (sball_c = 4) and (sball_c We need to pull ourselves up!");

4. Summing up the lesson. Reflection.

Self-assessment of students' work in class. Adequacy of student self-esteem with teacher assessment. Provide students with information about the real results of achieving the goals of the topic being studied. Making marks.

Reflection using the Cinquain technique:

noun

adjective adjective

verb verb verb

key phrase

noun

5. Information about homework.

Repeat materials §3.4, complete exercise 5 (§4).

Additional tasks to the lesson.

Strong students may be additionally offered the following task:

Task 5.

var a,b,x,y,NOD,NOK:integer;

write("x="); readln(x);

write("y="); readln(y);

if ab then a:=a-b

NOD:=a; NOK:= a*b div NOD;

writeln("NOK=",NOK)

Front work

Task 1. Under the influence of traction force F (N), the car travels a distance s (m). Determine the work done by force F.

Task 2. Enter the number. If the entered number is non-negative, then find the square root of the number, otherwise calculate the reciprocal number.

Task 1. Enter the height (in centimeters) of three girlfriends Masha, Natasha and Olya. Find out which of your friends is the smallest.

Task 2. Write a program to solve a linear inequality of the form a*x b

Task 3. Enter the number of students in the computer science group and each student's quarter mark. Calculate the average computer science grade point in the group for the quarter.

Task 4. Enter the number of marks in one of the subjects per quarter and the marks themselves. Output information about the average mark with commentary text.

Task 5. Find the LCM of two given numbers. LCM(a,b)=a*b/GCD(a,b).

Card for the lesson “Drawing up and implementing algorithms with branching and repetition.”

Front work

Task 1. Under the influence of traction force F (N), the car travels a distance s (m). Determine the work done by force F.

Task 2. Enter the number. If the entered number is non-negative, then find the square root of the number, otherwise calculate the reciprocal number.

Independent work on computers

Task 1. Enter the height (in centimeters) of three girlfriends Masha, Natasha and Olya. Find out which of your friends is the smallest.

Task 2. Write a program to solve a linear inequality of the form a*x b

Task 3. Enter the number of students in the computer science group and each student's quarter mark. Calculate the average computer science grade point in the group for the quarter.

Task 4. Enter the number of marks in one of the subjects per quarter and the marks themselves. Output information about the average mark with commentary text.

Task 5. Find the LCM of two given numbers. LCM(a,b)=a*b/GCD(a,b).

Card for the lesson “Drawing up and implementing algorithms with branching and repetition.”

Front work

Task 1. Under the influence of traction force F (N), the car travels a distance s (m). Determine the work done by force F.

Task 2. Enter the number. If the entered number is non-negative, then find the square root of the number, otherwise calculate the reciprocal number.

Independent work on computers

Task 1. Enter the height (in centimeters) of three girlfriends Masha, Natasha and Olya. Find out which of your friends is the smallest.

Task 2. Write a program to solve a linear inequality of the form a*x b

Task 3. Enter the number of students in the computer science group and each student's quarter mark. Calculate the average computer science grade point in the group for the quarter.

Task 4. Enter the number of marks in one of the subjects per quarter and the marks themselves. Output information about the average mark with commentary text.

Task 5. Find the LCM of two given numbers. LCM(a,b)=a*b/GCD(a,b).

noun

adjective adjective

verb verb verb

key phrase

In algorithmic structures, a cycle includes a series of commands that are executed repeatedly. This sequence of commands is called the body of the loop.

There are two types of cyclic algorithmic structures:

Counter loops in which the body of the loop is executed a certain amount of once;

Conditional loops in which the body of the loop is executed as long as the condition is true.

Algorithmic structure The cycle can be captured in various ways:

Graphically, using a block diagram;

In a programming language, such as Visual Basic and VBA, using special instructions that implement loops of various types.

Loop with a counter. When you know in advance how many repetitions of the loop body need to be performed, you can use the cyclic instruction (loop operator with a counter) For. . . Next (Fig. 19).

For statement syntax. . . Next is next: the line starting with the For keyword is the loop head, and the line with the For keyword

Next - end of the cycle; Between them are operators that represent the body of the loop.

At the beginning of the loop, the value of the Counter variable is set equal to StartValue. With each “pass” of the loop, the Counter variable is incremented by the step value. If it reaches the value ConValue, then the cycle ends and the following statements are executed.

Conditional loops. 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 must be done. In such cases, the number of repetitions depends on some condition. This loop is implemented using the Do... Loop instruction.

The condition for exiting the loop can be placed at the beginning, before the loop body (Fig. 20) or at the end, after the loop body (Fig. 21).

The loop exit condition is checked using the While or Until keywords. These words

They give the same condition the opposite meaning. Keyword While ensures that the loop runs as long as the condition is true, that is, as long as the condition evaluates to true. In this case, the condition is a condition for continuing the loop. As soon as the condition evaluates to false, the loop will end.

The Until keyword ensures that the loop continues until the condition is met, that is, until the condition evaluates to false. In this case, the condition becomes a condition for ending the loop. As soon as the condition evaluates to true, the loop will end.

11The concept of an algorithm. Algorithm executor. System of performer commands (using the example of a training performer). Properties of the algorithm. Methods for writing algorithms; flowcharts.

The appearance of algorithms is associated with the origins of mathematics. More than 1000 years ago (in 825), a scientist from the city of Khorezm, Abdullah (or Abu Jafar) Muhammad bin Musa al-Khorezmi, created a book on mathematics in which he described ways to perform arithmetic operations on multi-digit numbers. The word algorithm itself arose in Europe after the book of this mathematician was translated into Latin.

Algorithm– a description of a sequence of actions (plan), the strict execution of which leads to the solution of the task in a finite number of steps.

You constantly come across this concept in various areas of human activity (cookbooks, instructions for using various devices, rules for solving mathematical problems...). Usually we perform habitual actions without thinking, mechanically. For example, you know well how to open a door with a key. However, in order to teach this to your child, you will have to clearly explain these actions themselves and the order in which they are performed:

1. Take the key out of your pocket.2. Insert the key into the keyhole.3. Turn the key counterclockwise two times.4. Remove the key.

Types of algorithms:

1. Linear algorithm(description of actions that are performed once in a given order);

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

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

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

In practice, the most common are the following forms of representation of algorithms:

· In oral form.

· In writing in natural language.

· In writing in formal language.

· For a more visual representation of the algorithm, it is widely used graphic form – block diagram, which is composed of standard graphic objects.

Definition 1.4. Algorithmization is the process of developing an algorithm for solving a problem.

For some problems this process is quite simple, for others it requires some effort, especially in cases where the algorithm must satisfy predetermined conditions, for example, the maximum speed of solving the problem, minimum requirement to the amount of computer memory, etc. In this section, using examples of many problems from the simplest to relatively complex, methods for rationally composing algorithms are outlined. Problems are presented in mathematical or near-mathematical form. Moreover, they are selected in such a way that their solution does not require knowledge that goes beyond the mathematics course of secondary schools.

Experience in teaching programming shows that students often neglect drawing up flowcharts of algorithms. The desire to write a program faster gives rise to the feeling that drawing a flowchart is like extra work. This approach, however, is erroneous and should be suppressed at the very beginning of training.

Drawing up a flowchart before starting programming very often allows you to detect errors in solving a problem, thereby clarifying the algorithm and largely eliminating the labor-intensive search for errors when debugging the program. Practical experience programming indicates that a large proportion of the time allocated to compiling a program is spent by programmers on detecting logical errors, and qualified programmers are those who quickly eliminate these errors. In this regard, the role of algorithm flowcharting is extremely important.

In addition, flowcharts are needed to provide reporting on developments, as well as to familiarize stakeholders with them. Therefore, in the future, for most of the problems under consideration, either block diagrams of algorithms will be given, or their text form will be given, or both will be presented.

Now let's move directly to the consideration of problems and the design of algorithms for solving them.

Task 1.1. Given two real numbers A And b. It is necessary to find their sum 5, difference I, work R and private N from division A on b.

The algorithm seems obvious: enter numbers into the computer memory A And b, perform calculations 5 = A + b, I = a - b, P = a : b, H = a/b and display the results on the screen (printer). However, such an algorithm is incorrect for the case when b = 0. In this case, purely mathematically, we could write that N- a/b =co. However, in the computer, the operation of division by zero is not defined, as a result of which the message “division by zero” will be displayed on the display screen and the program calculation will be interrupted. Therefore, checking whether b zero, the algorithm must be provided for. The correct algorithm is shown in Fig. 1.3. Below is its text form.

Step 1. Enter A, b.

Step 2. Calculate B = a + b, I = a - b, P = ab.

Step 3. Withdraw I, R.

Step 4. If b= 0, go to step 7.

Step 5. Calculate N = a/b .

Step 6. Withdraw N and go to step 8.

Step 7. Withdraw b = 0, N - CO.

Step 8. Stop.

Problem 1.2. Given two real positive numbers A And b. Find the arithmetic mean and geometric mean of these numbers.

As is known, the average arithmetic numbers a, b defined as?= (A + b)/ 2, and the geometric mean as C =y[ab. Therefore, the block diagram of the algorithm is presented in Fig. 1.4. Its text form will be like this.

Step 1. Enter a, b.

Step 2. Calculate?= (a + b)/ 2, C = 4ab.

Rice. 1.3.

numbers a, b

Rice. 1.4.

Step 3. Withdraw (7. Step 4. Stop.

The above algorithm contains the operation of the geometric mean (7 = 4ab. It would seem that we should first calculate the value c=ab, and then, using, for example, Newton’s algorithm (see Fig. 1.1), calculate (7. However, in the set standard programs There is a computer program that calculates the square root of a positive number. Therefore, with appropriate access to this program, it will calculate (7.

Problem 1.3. Given two real numbers A And b. Determine which number is greater or whether they are equal. The algorithm for solving the problem is shown in Fig. 1.5.

Its text form is as follows.

Step 1. Enter A, Kommersant

Step 2. If A = b, go to step 6.

Step 3. If a > b, go to step 5.

Step 4. Withdraw b>a and go to step 7. Step 5. Withdraw a>b and go to step 7. Step 6. Withdraw A = b.

Step 7. Stop.

Problem 1.4.

Calculate the value of function 1 - X, If*

+ X 3. if 2

• 1/x 2 if 1

1 + x + x 2 if x > 3.

Calculation algorithm ? shown in Fig. 1.6. Its text form is as follows.

Step 1: Enter x

Step 2. If x 1, go to step 8.

Step 3. If x go to step 7.

Step 4. If l:

Step 5. Calculate ?= 1 + X + * 2 and go to step 9.

Step 6. Calculate ? = V1 + x 3 and go to step 9.

Step 7. Calculate ?= 1/x 2 and go to step 9.

Step 8. Calculate ?- 1 - x.

Step 9. Withdraw X, ?.

Step 10. Stop.

Problem 1.5. Create an algorithm for calculating the roots of a quadratic equation ax 2 + bx + c = a, b, c f 0 when a f 0, b f0, c f0.

As is known, depending on the sign of the discriminant c1 = b 2 - 4 ac quadratic equation ax 2 + bx + c = With real coefficients a, b, sf 0 can have three types of roots: different real roots if c1> 0, equal real roots, if c!= 0, and complex conjugate roots if With! 0. Different real roots are calculated using the formulas

Print x, U

~b + 4 g,

x, =-, x 2 =-. Equal roots are defined as follows: x, =

2 a " 2 A

= x 2 = -. Complex conjugate roots are calculated as follows: 2 A

• - imaginary part

the same as real ones, they are only represented by two numbers -b . l!4

- ± /--, where the sign / indicates that 2a 2a

root values. In connection with what is stated in the algorithm for calculating roots, the first stage should include the calculation of the discriminant value and further verification of its sign. The algorithm with maximum savings in computational operations is shown in Fig. 1.7. Below is its text form.

Step 1. Enter A, b, With.

Step 2. Calculate c1 = b 2 - 4ac, k = a + a, k = -b/k.

Step 3. If 0, go to step 7.

Step 4. If 0, go to step 6.

Step 5. Put x, = k and go to step 10.

Step 6. Calculate g = 4(4, g = g/h, x x = k + g, x 2 = k - g and go to step 9.

Step 7. Calculate g = y(4, g = g/h.

Step 8. Output: “Complex roots x, = /:+/>, x 2= /:-/>" and go to step 11.

Step 9. Print: “Real roots” x, x 2 and go to step 11.

Step 10. Output: “Roots equal to x, = x 2 ” x,.

Step 11. Stop.

Most of the above algorithms contain so-called branches, i.e. places in the block diagrams where calculations are sent along different paths. These locations are determined by value comparison blocks. From each block there are two outputs, one of which corresponds to the case when the comparison condition is satisfied (“yes”), the other to the case when it is not satisfied (“no”). Such algorithms are called branching algorithms.

Now let's look at algorithms that contain fragments of repetition of calculations - cycles. Depending on whether the number of repetitions of a certain section of the algorithm is known in advance or not, arithmetic and iterative cycles are distinguished.

In arithmetic loops, the number of repetitions of calculations is controlled by a control variable that acts as a loop counter. With each next calculation, the counter value changes by a specified value and is compared with the set number of repetitions. If these values ​​coincide, the repetitions stop, i.e., the loop is exited with a counter. Otherwise, the calculations continue to be repeated. If before the loop starts, the counter value exceeds the specified number of repetitions, it is not executed at all. It is also possible to force exit from the cycle according to some predetermined condition.

In iterative type loops, in which the number of repetitions is unknown in advance, they are terminated (exited from the loop) when a certain condition is met. Usually this condition is formulated, for example, like this: perform repetitions until x where With - a constant value (constant), ax-increases with each repetition (iteration). In the case when the condition is checked before the repetitions begin, the cycles are classified as cycles with a precondition; when this check is carried out after each iteration, they are classified as cycles with a postcondition. For the first group of cycles, if x>c, There will be no repetition of calculations at all; for the second one, at least one cycle will always be executed. All arithmetic loops are loops with a precondition.

Problem 1.6. Given a series of numbers x 15 x 2 ,..., X,-, ..., x p. Find their sum 5.

Since the sum 5 = x, + x 2 + ...+x,- + ... + x n and the summation of numbers is performed sequentially, i.e. 5 M is added to the found sum x, - number, then the calculation 5, = 5 M + x, - is repeated P- 1 time if you put 5 M =x x. Therefore, the algorithm for calculating the sum will be as shown in Fig. 1.8. Its text form includes the following actions.

Step 1. Enter x, ..., x p, p.

Step 2. Put 5=x,.

Step 3. Put / = 2.

Step 4. If /> P, go to step 7.

Step 5. Put 5=5+ x,-.

Step 6. Put / = / + 1 and return to step 4.

Step 7. Withdraw 5.

Step 8. Stop.

Rice. 1.8. Algorithm for calculating the sum P numbers

In this algorithm, the role of the loop counter is assigned to the variable /, which changes in steps of 1. If it were necessary to calculate the sum of numbers X ) , ..., x n through one number, then it is obvious that the step of changing the variable / should be taken equal to 2, and its initial value 3. Thus, in the fourth block of the algorithm diagram one should indicate / = 3, and in the seventh / = /" + 2.

Problem 1.7. Create an algorithm for calculating a function P(“l-factorial”). As is known, P - This work P natural numbers 1 2 3 ... P. In this case it is assumed that 1! = 1. Therefore, calculating the value P can be considered as a sequential repetition of the operation of multiplying the previous value of the factorial T 7 by the next natural number. Calculation algorithm P shown in Fig. 1.9.

Its text form is like this.

Step 1. Enter P.

Step 2. Put P= 1.

Step 3. Calculate /= 2.

Step 4. If / > P, go to step 7.

Step 5. Put G-Ya.

Step 6. Put /= /+ 1 and return to step 4.

Step 7. Output T 7.

Step 8. Stop.

In a similar way, you can build algorithms for calculating values 2", a p, Where A - real, and P - whole numbers.

Problem 1.8. Create an algorithm for calculating an expression k == ^2 + ^2~+ ^2 + ... + l/2 . It is easy to see that if as

P roots

take the initial value k =a/2, then the repeated action will be to evaluate the expression V2 + To. Therefore, the algorithm for solving this problem has the form shown in Fig. 1.10. Its text form is like this.

Step 1. Enter P.

Step 2. Calculate To= a/2.

Step 3. Put /= 2.

Step 4. If /> P, go to step 7.

Step 5. Calculate To= l/2 + k.

Step 6. Put /"=/"+ 1 and return to step 4. Step 7. Output To.

Step 8. Stop.

Problem 1.9. Create an algorithm for calculating an expression S== sin l: + sin 2 * ... + sin"*.

If we take the initial value of the sum S = s"mx, then the repeated action will be 5 + 5sin*. The algorithm that calculates the specified amount is presented in Fig. 1.11. Its text form is like this.

Step 1. Enter p, x.

Step 2. Calculate 5 = sin*.

Step 3. Put / = 2.

Step 4. If /> P, go to step 7.

Step 5. Calculate S=S+^sinx.

Step 6. Put / = / + 1 and return to step 4. Step 7. Output S.

Step 8. Stop.

Problem 1.10. Create an algorithm for calculating the mean square P real numbers x y, x 2, ..., x p.

It is known that the average vadratic n real

numbers is the value 5* = L - (x? + x + ... + x 2 p. Therefore al-

The algorithm will be like this (Fig. 1.12). Its text form includes the following actions.

Step 1. Enter Hu, ..., x„, p.

Step 2. Set / = 1.

Step 3. If /> P, go to step 7.

Step 4. Set ^ = 0.

Step 5. Calculate +x,-x g

Step 6. Put /=/-+- 1 and return to step 3.

Step 7. Calculate =8 k/p.

Step 8. Calculate =d/^7.

Step 9. Output Step 10. Stop.

Problem 1.11. Create an algorithm for calculating the number of combinations P numbers by T For n > t > 0.

Number of combinations of P By T, denoted by C"!, is calculated

according to the well-known formula C"" =

. It would seem that the construction

(p - t)t

algorithm does not cause problems: calculate values P,

• (P - T), T, using the algorithm for this (see Fig. 1.9), and then implement the formula to determine WITH"". This approach generally requires P - 1 + (P - T - 1) + t - 1 = 2/7-3 cycles. It is possible to construct an algorithm for calculating the value of C;, which will perform only T cycles. Then, in the worst case, when T just one less P, the number of cycles will be approximately 2 times less than 2/7. This algorithm is based on the use of a recurrence relation to calculate C"".

/ X 1 , . . . , X/; , AND

Rice. 1.12.

P real numbers

C, etc.

To construct the algorithm, we will write a general expression for calculating C"!, which we will calculate in a loop. According to the recurrence relation when T= 0 number of combinations С^ 1 = С 1 =

At t = i number of co-

= P. At t = 1 number of combinations S 2 p

And І +1 ^ I

reading C, =-

pi-1 U1 - 171 ^ sch і

It is written like this: C =

WITH"", C p = p and allows you to calculate combinations sequentially C = p, C 2 = ---S" p,

C" p. Since in the end it is necessary to obtain knowledge

reading C"" t then / should vary from 1 to T - 1. The block diagram of the algorithm is shown in Fig. 1.13. Its text form is like this.

Step 1. Enter p, t.

Step 2. If p display “Repeat input, p and return to step 1.

Step 3. If P= 1, go to step 10.

Step 4. If p = t, go to step 9.

Step 5. Put C=n, /= 1.

Step 6. If / > T - 1, go to step 11.

Step 7. Calculate C =- --WITH.

Step 8. Put /= /+ 1 and return to step 6.

Step 9. Put C= 1 and go to step 11.

Step 10. Put C=p.

Step 11. Withdraw WITH.

Step 12. Stop.

Note that the above block diagram provides for checking the correctness of entering numbers T so that p>t.

Problem 1.12. Design an algorithm for calculating a polynomial (polynomial) R p (x) degrees P for some real value x

Using the traditional form of polynomial representation r p (x) =a p x p + a p _ x x p ~ x + ... + a 2 x 2 + a x x + a 0, the algorithm is possible

it would be depicted as in Fig. 1.14.

Enter #o» 5 a p, x

	Y=UH, P = P + a, y

Rice. 1.14. Algorithm for calculating the polynomial represented by

in canonical form

This algorithm uses two multiplication operations and one addition operation in a loop. There is, however, another more quick way calculating the value of a polynomial. It is based on the use of Horner’s scheme, according to which the polynomial is represented as follows:

P"(x)= (...((a n x + a n _)x + a n _ 2)x + ... + a x)x + a 0 .

For example, for P= 4 it looks like this:

P„(x) =(((a n x + a b)x + a 2)x + a x)x + a 0 .

The algorithm that calculates the polynomial using Horner's scheme is shown in Fig. 1.15. In the loop it performs only one multiplication operation.

Problem 1.13. Develop a function tabulation algorithm y =/(x) on the interval [a, b], a with step Ax.

Tabulating a function usually means compiling a table of function values ​​at points a, a + Oh, A+ 2Ah, A+ /Ah, a + pAx of a given interval. An algorithm for solving this problem can be constructed using both arithmetic and iteration loops. In order to apply an arithmetic loop, you must first determine the number of tab stops P= --- . Then organize

repetition P times of calculating function values ​​at points A+ Ah, a + inax and add to its found values ​​the value /(A). The algorithm constructed using these comments is shown in Fig. 1.16.

Enter A, b, ah

Rice. 1.16. Algorithm for tabulating the function /( X) using

arithmetic loop

Its text form is as follows. Step 1. Enter A, b, Oh.

Step 2. Calculate n = --- .

Step 3. Calculate at = /(A), put x= A.

Step 4. Withdraw A, u.

Step 5. Put /= 1.

Step 6. If /> I, go to step 10.

Step 7. Put x = x + Ax, calculate y = Dx).

Step 8. Print x, u.

Step 9. Put /= /"+ 1 and return to step 6.

Step 10. Stop.

The algorithm for solving the problem using an iterative cycle is shown in Fig. 1.17.

In this algorithm, steps 7, 8 check whether the last tab stop of the function is the same as the end of the interval value b.

Problem 1.14. Create an algorithm for finding the greatest common divisor (GCD) of two integers a, b and the least common multiple (LCM) of these numbers.

As is known, gcd of numbers a, b - the largest integer that divides these numbers without a remainder. Least common multiples of integers A, b is an integer that is divisible by A And b. If the GCD is known, then the LCM is calculated using the following formula: LCM ( A, b) = ab/Oj(a, b). Therefore, before calculating the LCM, it is necessary to find the GCD.

There are several algorithms for calculating GCD. Let us present the simplest of them, which belongs to the ancient Greek mathematician Euclid. He noticed that GCD ( A, b) is equal to gcd ((A - b), b), Where a > b. Therefore, the essence of his algorithm comes down to sequential subtraction of a smaller number from a larger number until these numbers become equal to each other. The algorithm is shown in Fig. 1.18 and contains an iterative type loop.

The text form of the algorithm for calculating GCD, LCM is as follows.

Step 1. Enter a, b.

Step 2. Put u = a, v = b.

Step 3. If A = b, go to step 7.

Step 4. If a > b, go to step 6.

Rice. 1.17.

iteration loop

Rice. 1.18. Algorithm for calculating the greatest common divisor of numbers a, b and their least multiple

Step 5. Put x = a, a = b, b = x.

Step 6. Put x = a - b, a = x and return to step 3.

Step 7. Put GCD = A.

Step 8. Calculate LCM = And g/NOD.

Step 9. Withdraw A, b, NOD, NOC. Step 10. Stop.

Problem 1.15. Develop an algorithm for calculating the value of the chain

fractions U=---for x f 0.

As follows from the notation of the fraction, the last divisor in it is

The expression C = x + - is given, the value of which for a given x can easily be found. The penultimate divisor is

the expression C = x +

And I precede-

its common divisor is the expression C = x +- , where C -

the previously found value of the divisor. In this way it can

the value of the divisor can be found C = x + - , and then the value of the fraction Y = -.

Obviously, the repeated action in this problem is to find the next divisor. Considering that 2 = 2 1 and 256 = 2 8, a total of eight divisors need to be found. Excluding the last divisor, we get a total of seven repeating actions. Based on the above considerations, we construct an algorithm that calculates a given expression (Fig. 1.19). Its text form is like this.

Step 1. Enter x.

Step 2. Put a = xx, b = 256.

Step 3. Calculate With = A + b/a.

Step 4. Put і = 7.

Step 5. If i 1, go to step 8.

Step 6. Calculate b = 0,56, c = a + b/s.

Step 7. Put і - і - and return to step 5.

Step 8. Calculate Y=x/C.

Step 9. Withdraw y, x.

Step 10. Stop.

Problem 1.16. Given a series of numbers a x, a 2 , ..., A" ..., a p. Develop an algorithm for finding the largest and smallest number in this series, indicating the number (index) of its location.

An obvious way to find the largest (smallest) number in a given series P numbers includes the following steps. Take the first number of the series and say that it is the largest (smallest), and its index is 1. Then take the second number of the series and compare it with the supposed maximum (minimum) first number. If the second number is greater than the estimated maximum (minimum) first number, replace the first number with this number and set its index to two. If the second number turns out to be less than the first numbers, take the third number in the series and compare it with the first. Continue this way until the last one is selected. a p number. As a result, the first number will be replaced by the largest (smallest) number with its indicated number in the series of numbers. The algorithm that implements these actions is shown in Fig. 1.20. Its text form is as follows.

Step 1. Enter a x, ..., a p, p.

Step 2. Put max = a x, i - 1,min - a x, j - 1.

Step 3. Put k = 2.

Step 4. If and to max, go to step 6.

Step 5. Put max = a k, i = k.

Step 6. If a to> min, go to step 8.

Step 7. Put min = a k, j = k.

Step 8. Put k= k+ 1.

Step 9. If k return to step 4.

Step 10. Print max, /", min, y.

Step 11. Stop.

Problem 1.17. Given a series of numbers a x, a 2, ..., a„ ..., a p and number b. Construct a search algorithm for a number series and to, equal b, and messages whether the number was found or not.

Rice. 1.20.

in a sequence of numbers

The solution to this problem comes down to sequential comparison of numbers in the series a ( , a 2 , ..., a p with number b, number output and to, coinciding with b, and its index To or displaying a message that the required number was not found. An obvious algorithm for solving it is shown in Fig. 1.21.

Enter SLI ...,7, b

This algorithm in the worst case, i.e. when the number is not found, executes 2 P comparisons. At the same time, there is an algorithm that, when p> 8 significantly reduces this number, and therefore the search time. The improved algorithm is shown in Fig. 1.22. Reducing the number of comparisons is achieved by eliminating constant comparisons/s P, characteristic of the first algorithm. The loop exits either when A, = b, or when on ( n+ 1)th repetition the number will be revealed b, recorded in (n + 1)th cell of the array.

The last two tasks are classified as processing arrays - sets of data of the same type - numbers or symbols. In programming, a distinction is made between one-dimensional and multidimensional arrays. A one-dimensional array is formed by its successive elements. The place of an element in the array is determined by its number - the index, which is a positive number. Number sequences considered A., a b

b are one-dimensional arrays.

Two-dimensional arrays are rectangular tables of data consisting of a specified number of rows and columns (columns). In mathematics, such tables are called matrices and are very widely used both directly in mathematical calculations and in programming. A matrix element is placed at the intersection of a row and a column and is identified by two indices: a row number, such as /, and a column number, such as y. If the matrix contains T lines and P columns, total elements of this matrix tp And A ] - its arbitrary element. Matrix containing T lines and T columns is called rectangular.

In a square matrix, there are main and secondary diagonals. Matrix A = a c size t x p, i.e. containing T lines

And P columns, t = n, has the form:

		(1 )SH

The main diagonal of the matrix is ​​formed by the elements a and, a 22, ..., and so on, i.e. elements lying on a straight line drawn from left to right from the element a p to element and so on.

The side diagonal is formed by the elements of the matrix a 1p, a 2p _ x, ..., and t1, lying on a straight line drawn from the element a 1p to element and t( , i.e. from right to left.

The elements of matrix A lying to the right and above the main diagonal form the upper triangular matrix. The elements lying below the main diagonal to the left form the lower triangular matrix.

A matrix is ​​called symmetric if the elements symmetrical with respect to the main diagonal are equal to each other, i.e. a and= th/(.

One of the most important tasks in processing one-dimensional arrays is their sorting - the arrangement of array elements in a certain order. Most often, we consider ordering the elements of numeric arrays in ascending or descending order. According to statistics, approximately 25% of computer time is spent on sorting data, because sorted data is much easier to process. When array elements are sorted, it is faster to find them, update them, exclude them from the array, etc.

There are a number of sorting algorithms. Their average operating time or time complexity ranges from 0(p 2 / 4) up to 0(ppp), Where P - number of array elements. Unfortunately, there is no sorting algorithm that is best in any case.

Let's look at the simplest sort, called insertion sort. The idea of ​​this sorting is that the next (sorted) element of an array, ordered, for example, in ascending order, is compared with its previous elements until an element less than or equal to it is encountered. Then all elements following the smaller element are shifted one position to the right, and the next element is placed in the free space behind the smaller element. If, as a result of comparing the element being sorted with previous elements of the array, a smaller element is not found, the element being sorted is left in its old place and the next element of the array is moved on. Comparisons start with the second element of the array and end with the last element.

Consider this sorting on an array of integers

• 71 27 412 81 59 14 273 87, which needs to be sorted in ascending order. The first element of the array to be sorted is the second element - the number 27. Figuratively speaking, we “remove” it from the array, i.e., we make room for a future shift of numbers to the right, and compare the second element (number 27) with the first element (number 71). Since 27
• 27 71 412 81 59 14 273 87,

in which part of the array 27, 71 is pre-sorted.

Now we select the third element of the array - the number 412. We remember it and compare it with the previous element of the array. Since 412 > 71, and 71 > 21, we leave the number 412 in its place, i.e. we get the same array

27 71 412 81 59 14 273 87.

We select the fourth element of the array - the number 81. We remember it and compare it with the previous element - the number 412. Since 81

27 71 81 412 59 14 273 87.

We select the fifth element of the array - the number 59. We remember this number and compare it with the previous element of the array - the number 412. Since 59 59, we shift it one position to the right. It is easy to see that the process of comparing and shifting elements will end at the number 27. As a result, we get

27 59 71 81 412 14 273 87.

The sixth element of the array is the number 14. By comparing it with the previous elements and shifting them to the right, we get the array

14 27 59 71 81 412 273 87.

Having performed the described actions with the seventh and eighth elements of the array, we obtain a sorted list

14 27 59 71 81 87 273 412.

Problem 1.18. Develop an insertion sort algorithm.

According to the described sorting method, the general repetitive action is to select the next element to be sorted and remember it. Elements are selected starting from the second and ending with the last um element of the array. These actions will form the outer loop of the algorithm. The inner loop of the algorithm consists of the actions of comparing and, if necessary, shifting elements, as well as inserting them into the required position of the array. Therefore, the algorithm implemented by the method under consideration will look like this (Fig. 1.23). Its text form is as follows.

Step 1. Enter i, ..., a p, p.

Step 2. Put / = 2.

Step 3. Put To= I,

Step 4. Put y = /"- 1.

Step 5. If To > a p go to step 8.

Step 6. If you

Step 7. Put a ]+x = a p y = y - 1 and return to step 5.

Step 8. Put i /+1 = k, /= / + 1.

Step 9. If /n, go back to step 3.

Step 10. Output i, ..., i„.

Step 11. Stop.

Checking the condition y > 0 in the above block diagram is necessary so that when comparing the sorted element To with previous ones a p i-_, i, do not go beyond the array. Otherwise the algorithm will not be defined. In conclusion, we note that insertion sort according is quite effective for arrays with a maximum number of elements P 0(n 3/2), and quick sort, the average complexity of which is 0(1n(i)). Typically, this sorting is used for arrays with a number of elements P > 1000.

In cases where a search for elements is constantly carried out in a certain array, this array is pre-sorted and then the search is carried out in an ordered manner.

Rice. 1.23.

array. The most commonly used search algorithm is the so-called binary search. Practice shows that this approach significantly reduces the average time spent on searching.

The essence of binary search is as follows. Let an array of numbers ordered in ascending order be given a x, a 2, a p a p and number b. Need to find an array element and to, equal b, or report that there is no such element in the array. Let's denote the first index of the array /, and the last And. Then the index of the number a p standing approximately in the middle of the array, can be found by the expression y = |(/ + and)/ 2_|, where the characters |_ ] define the integer part of the number (/ + And)/ 2. If

I- = b, the search process is completed. If b then due to the ordering of the array i, ..., a p the required number will be in the subarray A" ..., a ] _ 1 . When b > a p then for the same reason the number should be looked for in the subarray i y+1, ..., a p. Thus, as a result of choosing the number A ] and comparing it with a number b you can proceed to searching in an array with the number of elements 2 times less than P. Next is the process of selecting the element I. is carried out in one of the subarrays, reducing the search in an array with the number of elements 2 times less than in the subarray. This selection process A ] and dividing the next array in half continues until the specified number is found or it is determined that it is not in the array. We will demonstrate the described process by searching for an element b= 59 in the next array

14 27 59 71 81 87 273 412 501.

The array contains nine elements, so y = |_(1 + 9)/2_| =

5. The element with index 5 is a 5= 81. Compare it with b= 59. As a result, we proceed to search in the array 14 27 59 71 (/= 1, And=y - 1 = 5 - 1 = 4). Now we calculate the index y = |_(1 + 4)/2_| = 2.

The element at index 2 is a 2= 27. Compare it with b= 59. As a result, we proceed to search in the array 59 71 (/=у+1 =

2+1 = 3, And= 4). We calculate the index y = |_(3 + 4)/2_| = 3. Element

with index 3 - this is I 3 = 59. Compare it with b= 59 and establish that this is the desired array element.

Now consider the case when the element b= 12, i.e. it does not belong to the array. The first index is y = 5 and we proceed to search in the array 14 27 59 71 (/ = 1, And= 4). The second index y = 2, which gives the next search array 14 27 (/= 1, u = 2). Third search index y = 1(1 + 2)/2 I = 1 and we move on to search array 14

(/ = 1, And= 0). However, there is no element with index in the array And= 0. This means that we checked the entire array and did not find element i; = b. Thus, we can conclude that the sign of the absence of an element in the array is the inequality And

Problem 1.19. Create a binary search algorithm.

Taking into account the above, we can propose the following algorithm for solving this problem (Fig. 1.24). Its text form is given below.

Rice. 1.24.

Step 1. Enter a x, a p, p, b.

Step 2. Put / = 1, And = P.

Step 3. If and go to step 9.

Step 4. Calculate |_(/ + «)/2_|.

Step 5. If A ] = b, go to step 8.

Step 6. If a/put And=y - 1 and return to step 3.

Step 7. Set / = y + 1 and return to step 3.

Step 8. Print “Element found”, y = and go to step 10.

Step 9. Display “Element not found”.

Step 10. Stop.

The idea of ​​binary search is used in other cases, in particular when calculating the roots of transcendental and algebraic equations. Let a transcendental equation be given, for example e x - x - 2 = 0, and it is known that its root belongs to the interval [a, b. You need to find the value of this root.

In general, the equation can be written as /(x) = 0, where Dx) is a continuous function considered over the interval [a, b]. Since the solution to the equation, i.e. its root, x e [a, b] turns the equation into an identity, then the left side of the equality /(x) = 0 at the point x e a, b] must be equal to zero. From a geometric point of view, this means that the function /(x) at point x intersects the abscissa axis. This intersection point must be found.

To do this, we proceed as follows. By expression IV= (a + b)/2 find the coordinate IV midpoint of the segment [a, b. If Dx) = 0, then the root of the equation x = IV found. If /( A)/(VO > 0, i.e. /( A) and /(BO of the same sign, there is no root on the interval (Fig. 1.25), and we proceed to searching for it on the interval , which is half as long as the original interval [a, b]. If /( A)/(VO a) and /(VO different signs, the root is on the interval [a, IV], and its search is carried out on this interval, and the interval [ IV, b] is forgotten.

Thus, evaluating the expression Ts^=(a+b)/2 and performing the comparison /(i)/( IV)> 0, we reduce the search interval by exactly half. As a result, after P of such actions we get the interval [a p, b p], which contains the root of the equation, 2" times smaller than the original interval [a, b, i.e. a p - b p = A -^/2". Taking as the accuracy of calculating the root a the length of the interval | a p - b p, you can determine what needs to be done to obtain this accuracy n = na - b|/e steps. The described method

Rice. 1.25.

root search is called the method of halves, or dichotomies.

Problem 1.20. Develop an algorithm for refining the root of the equation /(x) = 0 using the dichotomy method.

The method assumes that the interval is specified a, b, to which the root belongs, the function /(x) = 0 is continuous and bounded on this interval and f(a) f(b)

Step 1. Enter a, b, e.

Step 2. Put and =/(i), v = f(b).

Step 3. Calculate x = a + , w = f(x).

Step 4. If w = 0, go to step 10.

Step 5. If uw> 0, go to step 7.

Step 6. Put b = x, v=w and go to step 8.

Step 7. Put a = x, u = w.

Step 8. If a - b > s, return to step 3.

Step 9. Put x = a - b.

Step 10. Withdraw X, s.

Step 11. Stop.

When solving various problems, it is often necessary to use the values ​​of elementary functions such as sin (x), cos (x), log (x), In (x), e x etc. In order to facilitate the calculation process

u=/(a), y=/(6)

x = (a + b)/ 2, №=Ah)

b=x,y = 1G

Rice. 1.26.

implementation of these functions, in system library The computer stores pre-compiled programs for calculating their values. To use them, you just need to mention the name of the function and specify its argument. In its turn specified programs compiled on the basis of formulas for the series expansion of a particular function. For example, the function e x seems to follow

blowing endlessly nearby e x= 1 + X +-+

For the functions sin(x), cos(x), we respectively have:

. , V X X

In each of these expansions, the accuracy of the representation of a particular function is determined by the number of terms in the series. The larger this number, the more accurately the function is calculated for the same x. Therefore, to calculate the value of a function with a given accuracy c proceed as follows. The terms of the series are calculated and summed until the next term becomes less than 8 in absolute value.

Star 1.21. Create an algorithm for calculating the function zm(x) with an accuracy of 8 using its series expansion.

From the formula that approximately represents the function bsh(x) in the form of an infinite series, it follows that the algorithm for calculating the value of 8w(x) with a given accuracy e will include repeated actions of calculating the next member of the series, summing the terms of the series and changing the sign of the corresponding member of the series. It is easy to see that each next term of the series U p and can be calculated using the recurrence formula U p =

For example,

at xx2 _ * 3 y _y

• 1 2 1 (2 1+1) 3!’ 2 1
• 2l(2 T) 3!- 4-5 5!

The signs of the members of the series change alternately, if you start with U x.

Therefore, the initial settings of the algorithm will be as follows ?=x, 6’ = x, Z= xx, a = - 1. In the loop we will calculate the next

series member ? = --- and add it to the previous one

2p(2p + 1)

sum with the corresponding sign. The block diagram of the algorithm is shown in Fig. 1.27. Its text form is given below.

y = x, 8 = x,

?-xx,a -~

Rice. 1.27.

Step 5. Calculate 6’= 5 + u.

Step 6. If at

Step 7. Put a = -a, n = n + 1 and return to step 4. Step 8. Print 5, x, e.

Step 9. Stop.

Problem 1.22. Create an algorithm for calculating the square trace

a 2 a

a, L a

	... sі pp

Step 1. Step 2. Step 3.

Enter x, e.

Put y = x, 5 = x, Z= xx, a = Put n= 1.

Calculate k= 2p, U =

k(k + 1)

A, A

matrix A =

As was said earlier, the trace of a matrix is ​​the sum of elements

ments of its main diagonal, i.e. I, - ^a i. Therefore the algorithm

determining the trace is reduced to calculating the sum. The block diagram of this algorithm is shown in Fig. 1.28.

However, there is a way to build a more efficient algorithm for solving this problem. It is based on calculating the address of the next diagonal element of matrix A not in a two-dimensional, but in a one-dimensional array.

It is known that elements of two-dimensional and large-dimensional arrays in computer memory are written linearly. Below, as an example, is a linear representation of the elements of matrix A with three rows and columns.

Through the indices of rows and columns /, y, the number of any element in a linear array is calculated using the formula x = (/ - 1)i+/ For example, the element number a 22 is defined as (2 - 1)3 + 2 = 5. Thus, to select any element from the linear

Rice. 1.28.

array, it is necessary to calculate its number using the expression A / "= (/- 1 )p + y, that is, perform three arithmetic operations.

At the same time, you can see that the number of the next diagonal element in the linear array differs from the number of the previous diagonal element by a constant value k = n + 1. For example, number a 22- 5 is equal to number a p- 1, i.e. 1 +4 = 5. Therefore, in a linear array, the next diagonal element is determined by the number / = / + To. As a result, its calculation requires performing only one instead of three arithmetic operation, which generally leads to a reduction in the amount of calculations and an increase in the performance of the algorithm. The block diagram of this algorithm is shown in Fig. 1.29.

Problem 1.23. Develop an algorithm for calculating the sum of elements of the side diagonal of a square matrix A.

As an example, consider a matrix with three rows and

three columns A =

Rice. 1.29. An efficient algorithm for calculating the trace of matrix A

Through side elements

A straight line is drawn along the diagonals of this matrix to highlight them. The first index of the diagonal elements is the row number /, the second, as you can easily see, is calculated by the expression y = n + 1 - /", where k - p+ 1. Therefore, the block diagram of the algorithm that solves this problem will have the form shown in Fig. 1.30. Its text form is given below.

Rice. 1.30. Block diagram of the algorithm for calculating the sum of the elements of the side

diagonals of square matrix A

Step 1. Enter P, elements of matrix A.

Step 2. Put it down? = 0, / = 1, k= n + 1.

Step 3. Calculate? p = + a 1k _ g

Step 4. Put / = /" + 1.

Step 5. If /n, return to step 3.

Step 6. Withdraw $r.

Step 7. Stop.

Obviously, to solve this problem it is also possible to construct a faster algorithm, which is based on the selection of elements from a linear array.

Problem 1.24. Draw a block diagram of an algorithm that calculates the sum of elements of the upper triangular matrix A.

Consider a matrix A consisting of P lines and P columns.

		S1 pp

It is easy to see that the first index is

ment of the upper triangular matrix is ​​the row index /. The second index is determined by the expression y = / + 1. Therefore, the block diagram of the algorithm will have the form shown in Fig. 1.31. The algorithm has two loops: one external and the second internal. Such loops are called nested. The text form of the algorithm is given below.

Step 1. Enter P, elements of matrix A.

Step 2. Set A t = 0, /"= 1.

Step 3. Set y = / + 1.

Step 4. Calculate A, = 5 T + a c.

Step 5. Put y = y + 1.

Step 7. Put /"=/"+ 1.

Step 9. Output A t.

Step 10. Stop.

Problem 1.25. Draw a block diagram of the algorithm for obtaining the transposed matrix A, in place of the original square matrix A.

A square matrix A is said to be transposed with respect to a given matrix A if its elements are obtained by exchanging elements that are symmetrical with respect to the main diagonal

. We see what's in it

elements i 12 and a 2( , a n = a p Then to obtain A,. in the loop you need to remember the element And = a 1p in place of the element A ] put the element a p and in place of the element a m - element a 1) . The block diagram of the algorithm that solves this problem is shown below in Fig. 1.32. Its text form is as follows.

Step 1. Enter P, elements of matrix A.

Step 2. Set / = 1.

Step 3. Set y = 1.

Step 4. Put and =

« = a P

Step 5. Put y = y + 1.

Step 6. If y, go back to step 4.

Step 7. Put /"=/"+ 1.

Step 8. If /n, return to step 3.

Step 9. Output A,.

Step 10. Stop.

In matrix algebra and its applications, it is very often necessary to multiply the matrix A by a column vector b and multiplying matrix A by matrix B. How the multiplication operation is performed A on b, let's look at the example of the matrix

as a result of multiplication we get a column vector AB with elements of scalar products of matrix A rows and column b. The first element of this column vector

a x b = a and b x + a n b 2 + a n b 3 = ^ a and b ] -

Its second element

a 2 b = a 2 b + a 22^2 + “2з^з = У,”?/

Third column element

"z b = a 31 b 1 + a 32 b 2+ b 3 = ? a y b) .

Rice. 1.32. Block diagram of the algorithm for transposing a square matrix A

Thus, to multiply matrix A by vector b, it is necessary to sequentially multiply the string vector A per column b. In this case, multiplication A on b occurs only when the number of columns of matrix A is equal to the number of elements of the vector b.

Problem 1.26. Develop an algorithm for multiplying matrix A by vector b. Obviously, the algorithm must cyclically calculate the scalar product of each row vector of matrix A and the vector b and be remembered as an element of the resulting column vector Lt. The block diagram of the algorithm is shown in Fig. 1.33. The text form is given below.

Step 1. Enter p, t, elements Lee B.

Step 2. Put /= 1.

Step 3. Set y = 1, A* = 0.

Step 4. Calculate A* = 5* + a^b g

Step 5. Put y = y + 1.

Step 6. If y, go back to step 4.

Step 7. Put A" = 5*.

Step 8. Put /= /"+ 1.

Step 9. If /t, return to step 3.

Step 10. Withdraw A"".

Step 11. Stop.

Matrix multiplication A =				to matrix B =

is possible only when the number of columns of matrix A is equal to the number of rows of matrix B.

Multiplication is performed sequentially. First, matrix A is multiplied by the first column vector IN and get the vector C,. Then A is multiplied by the second column vector IN and get vector C 2 . This process is continued until the columns of matrix B are exhausted. As a result, matrix C is obtained with the number of columns of the second matrix B.

Problem 1.27. Develop an algorithm for multiplying matrix A by matrix B.

Obviously, in the algorithm, as a fragment of it, you can use the matrix-vector multiplication algorithm. The block diagram of the algorithm is shown in Fig. 1.34. On this block diagram To - number of columns of matrix B,

Step 1. Enter p, t, To, elements A, V.

Step 2. Put d = 1.

Step 3. Put /"= 1.

Step 4. Set y = 1, 5* = 0.

Step 5. Calculate 5* = I k + a 1) b k.

Step 6. Put y = y + 1.

Step 7. If you

Step 8. Put A," =

Step 9. Put /"=/"+ 1.

Step 10. If /"

Step 11. Put d = d + 1.

Step 12. If d return to step 3.

Step 13. Withdraw A™.

Step 14. Stop.

Let us pay attention to the fact that this algorithm has a system of two nested loops. The previous algorithm diagram has one nested loop.

Problem 1.28. Develop an algorithm for solving the system P linear equations with P unknown

			+ a 1p x p
	N" ?/97 X?)		+ a 2p x p
	+ a n2 x 2		+ a pp X p

Gaussian elimination method.

The essence of the Gauss method is that the first unknown x is first eliminated from all equations except the first. Then the second unknown x 2 is eliminated from all equations except the first two. Last excluded P- 1 unknown x„_, from the last two equations. As a result, a system of triangular equations is obtained

a" p x 1 + a[ 2 X 2 + ... + a n x n = b[ a 22 X 2 + ... +a 2 n x n = b 2

from which the unknown is first found x p = b" p 1a" pp, then using the value substitution method x n into the previous equation the next unknown then

X„-2 = (b"„-2 -a"b--a" t x„)/a" t _.

and end this process by calculating the value

Xi = (b[ -a" 22 x 2 -... -a" pp x p)/a" p.

Thus, the method contains two stages: sequential elimination of unknowns and sequential calculation of them. Let's consider the technique of eliminating unknowns using the example of three equations with three unknowns. For this, the system of equations

ry-columns of unknowns and right-hand sides of equations. Further races

a 2 a 2 2 a 23

look at the extended matrix A" =

In the first column of matrix A" we find the largest non-zero element in modulus. If there is no non-zero element in the column, the considered system of equations has no solutions. If the largest non-zero element is contained in any row of matrix A" except the first, we swap this row of the matrix A" with its first line. These actions control the compatibility of the system of equations and reduce the sensitivity of the method to the rounding of numbers that accompanies computer calculations.

In order to eliminate the first unknown x from the second equation of the system, we calculate the factor t 2 = a 2x / a n, multiply the first row of matrix A" by this factor and subtract the result of the multiplication from the second row A".

(I'm 21 - t 2 a i)x y - (and 22 - t 2 a p)x 2 - (a 23 - t 2 a xs)x 3 = b 2 - t 2 b x. I designated it as 2! - t 2 a and =a" 2x= 0, we will have

I 13 x 3 + I 23 x 3

a and X 1 + a p X 2 O + a" 22 x 2

"31* | + a 32 x 2

To exclude the unknown X ( from the third equation of the resulting system we calculate the factor t 3 = a zx/a and, Let's multiply this factor by the first row of matrix A" and subtract the result of the multiplication from the third row.

Then due to the fact that a m - t 3 a and= 0 and introducing the appropriate notation, we obtain the system

I am 13 x 3 + a 23 x 3

OH + A 12 x 2 O + a" 22 x 2 O + I 32 x 2

in which the unknown x is excluded from all other equations except the first.

Now the task is to eliminate the unknown x 2 from the third equation. To do this, we will do the same. Let's find the factor t" 3 =a" 32 /o" 22, Let's multiply the second equation by it and subtract the result of the multiplication from the third equation. As a result we get

(“32 - ^з«22)*2 “(«33 - ^3«2з)*3 = ^3 - t b ^2

Considering that a" 32 - t" 3 a" 22 = 0 and designating a" 33 - t" 3 a" 23 = a 33, b" 3 - t" 3 b" 2 = b 3, let's arrive at a triangular system

from which, using the method of sequential substitution, we obtain the values ​​of the unknowns

*3 =?з"Мз> *2 =(b" 2 -a" 23 x 3)/a 22, x 1 =(b X-i 13 x 3 -a p x 2)/a p.

Summarizing the above, we can say that the algorithm must perform P- 1 exception action P- 1 unknown. If To - number of the excluded variable, then in each of these actions it is necessary to do from / = To+ 1 to P subtracting equations. In this case, each subtraction is carried out by performing y = k + 1 to P arithmetic operations. In addition, for each elimination of a variable, it is necessary to find the maximum element in the corresponding column of matrix A. And the last thing to do is to calculate the values ​​of the unknowns x p,..., X,. Thus, the general enlarged block diagram of the algorithm appears as follows (Fig. 1.35).

Now let’s create algorithms for searching for the maximum element, subtracting rows and calculating the values ​​of variables, which are represented in this diagram by enlarged blocks.

Finding the index of the maximum element in a series of numbers is considered in Problem 1.16. In this case, it is no different from the method outlined there. We assume that the maximum element is the first in the column Whether 1 = k. Then, in a loop, we compare the remaining elements of this column with this element and thereby select largest element and set its index. The algorithm for searching for the minimum element in a column of matrix A is shown in Fig. 1.36. A fragment of checking the compatibility conditions of a system of equations is also shown there. In Fig. Figure 1.37 shows a block diagram of the row subtraction algorithm.

Algorithm for determining variable values x p, x p_x,..., x, consistently implements the formulas by which these variables are calculated x p = b p /a pp, x i _, = (b p_x - a p _ x x p)/a p _ x.... Its block diagram is shown in Fig. 1.38. Below is the text form of the complete algorithm.

Step 1. Enter p, A, V.

Step 2. Put k= 1.

Step 3. Put 1=k, / = To + 1.

Step 4. If | a 1k >a, k, put / = 1.

Step 5. Put / = / + 1, if / n, return to step 4.

Rice. 1.35.

		System
		incompatible

	* &kr I k/ Shchr a and = g, 7=7 + 1
	^=6*, = bі,

Rice. 1.36.

and replacing strings A"

Rice. 1.37.

Step 6. If a 1k= 0, go to step 29.

Step 7. If 1=k, go to step 12.

Step 8. Put y = To.

Step 9. Put I = a cr a k] = a / r a y = I-

Step 10. Put y = y + 1, if / n, return to step 9.

Step 11. Put? = b k, b k = b„ b, = I-

Step 12. Put /=? + 1.

Step 13. Calculate t = a)k /a kk, put a 1k = 0.

Step 14. Put y = k + 1.

Step 15. Calculate a 0 = a u - ta 1k .

To the conclusion

Step 16. Set y = y + 1, if / n, return to step 15. Step 17. Calculate b i = b; - t b k.

Step 18. Put / = / + 1, if /" n, return to step 13. Step 19. Put k - k+ 1 if k - 1, return to step 3. Step 20. Calculate x p = b p /a pp.

Step 21. Put i = n - 1.

Step 22. Put 5=0.

Step 23. Put = / + 1.

Step 24. Calculate 5=5+ a and x].

Step 25. Put y = y + 1, if y = i, return to step 24. Step 26. Calculate X,= (6, - 5)/i„-.

Step 27. Put / = /- 1, if /> 1, return to step 22. Step 28. Print x, ..., l:, and go to step 30.

Step 29. Print “The system is incompatible.”

Step 30. Stop.

Problem 1.29. Design an algorithm for writing a sequence of numbers 1, 2, 3, ..., 49 into a square matrix A with 7 rows and 7 columns in a spiral (Fig. 1.39).

Rice. 1.39.

The simplest solution to this problem is the following. Moving in a spiral, compose two sequences of indices of elements of matrix A. In the first sequence, enter the value of the indices of rows 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 7, 7, 7 , 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, ..., in the second sequence - the index values ​​of columns 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, ... . Then organize a cycle from 1 to 49, in which you sequentially select numbers from two sequences - the indices of the corresponding element of matrix A and, using these indices, replace the matrix element A ] enter the value of the loop control variable To.

Let / be the row indices of the matrix A, y are the indices of its columns, To - loop control variable. Let further 4 - k-e the value of the string index, and ] k - k-e the value of its column index. Taking into account these notations, the algorithm will have the form shown in Fig. 1.40.

Rice. 1.40. Algorithm for writing natural numbers 1, ..., 49 into matrix A

in a spiral

The disadvantage of this algorithm is that it is first necessary to create sequences of indices representing the spiral movement, and then program it.

It is possible to propose another algorithm in which only the initial and final indices of the sides of the spiral are recorded. For example, for its first four sides we get:

/= 1, y = from 1 to 7;

/" = from 2 to 7, U = 7;

/ = 7, y = from 6 to 1;

/ = from 7 to 2, y = 1.

For the remaining two spirals, we will find the indices in a similar way, based on the pattern of the spiral.

Thus, according to this approach, to write the numbers of one spiral into matrix A, it is necessary to perform four cycles: two in the forward direction and two in the reverse. To limit ourselves to using only these four cycles, it is necessary to find how the indices change depending on the helix number. Then the algorithm will contain one outer and four inner loops, the starting and ending indices of which depend on the indices of the outer loop. We present the refinement of this algorithm as an independent exercise.

Problem 1.30. Consider a chessboard and two positions of a knight on it (Fig. 1.41). Possible moves of the knight are shown by arrows and numbered. The knight on the left (square (1,2)), without going beyond the board, can only move three squares. The knight on the right (field(5,6)) can move to eight squares, which is the maximum

the smallest number of permissible moves of a knight from one FIELD. A knight's route is the sequential movement of a knight along squares of the board such that it does not end up on the same square twice. The end point of the route is a square from which there is no legal move, either because the knight leaves the board or because it re-enters some square of the route. Create an algorithm that constructs the knight's route as long as possible.

Obviously, the longest route is 63 squares of a chessboard. You can try to find such a route by searching through all the knight's routes starting from all 64 squares. Therefore, in addition to the route construction procedure, the algorithm must contain a cycle of 64 repetitions of specifying the source field.

In order to construct a knight's route starting from any square of the board, in addition to taking into account the restrictions that ensure a valid move, it is necessary to determine a strategy for choosing the next move. A possible such strategy could be the first legal move of the knight, if you look at its moves clockwise (see 2nd position of the knight, Fig. 1.41). In the case where there is no valid move, the route is considered completed.

In turn, the admissibility of a move under the condition of not hitting an already traversed route field can be determined as follows. We will write the value zero in all fields of the board, and we will number the further moves of the knight from a certain field with the numbers on which the knight makes the next move. Then a valid field will be a board field with a value of zero, and maximum number natural row at the end of the route will determine its length.

The knight's exit from the board can be detected by framing the board with two fields in which an arbitrary number greater than zero is written, for example 66. In Fig. Figure 1.42 shows the initial data about the board and shows the beginning of the knight's route from square (7, 8).

Based on the above, the algorithm for finding the best route for the horse should include the following steps:

• 1) initializing the board framing fields, i.e. writing the number 66 or any other number, for example 99, into these fields;
• 2) initialization of the beginning of the cycle for all routes indicating the initial route length / = -1 to select the best route;

Rice. 1.42. Initial data about the board and the beginning of the knight's route

• 3) initializing the fields of the board, i.e. writing the number 0 to these fields;
• 4) constructing the knight’s route, remembering its length and highlighting the best current route;
• 5) output of the best route and its length.

An enlarged block diagram of the algorithm for finding the best route for a knight is shown in Fig. 1.43.

In Fig. Figure 1.44 shows a block diagram of the algorithm for initializing the upper frame of the board, taking into account the fact that the entire board with the frame is a square matrix /) = 11

with 12 columns and 12 rows, i.e. two-dimensional array.

The block diagram for initializing the lower frame of the board will have a similar appearance. Only the starting and ending values ​​of the control string will be different / 5 = 11, 1 P = 12.

As for initializing the left and right edges of the board, in this case you can do without a nested loop over y. The block diagram of this algorithm is shown in Fig. 1.45. Sequentially connected block diagrams for initializing the top, bottom, and left and right frames of the board form a common block diagram for initializing the board frame.

Length Determination P route

Remembering the best route and its length / = /7

I*-:

Rice. 1.44. Flowchart of the initiation algorithm Fig. 1.45. Algorithm flowchart

lization of the upper frame of the board initialization of left and right

framing boards

The block diagram of initialization of the chessboard itself implements the procedure for entering it into a two-dimensional array /) = dyW with indexes / 5 =3, 1 P = 10, 5 =3, ] p = 10 values s1 1G She

can be easily constructed; therefore, it is not given.

Now let's look at how the algorithm for constructing a knight's route can be presented. Let us agree that the sequence of fields from which the knight's route begins will be specified using two indexes - the row / matrix O and its column y. Then according to Fig. 1.42 the indices of all squares that a knight can get to from an arbitrary square (/, y) going clockwise will be as follows.

	1 = 1 + 2

Thus, for the source field of the next route and each valid field (/,_/"), it is necessary to organize a review of a maximum of 8 fields. To do this, you should organize a loop of the variable by To from 1 to 8. In turn, the change in the index is conveniently calculated as / = / + 4, y = y + y*. For this value 4? A must be represented by two one-dimensional arrays 4 = (-2 -112 2 1-1 -2), y4 = (1 2 2 1-1-2-2 -1).

Based on the above, the construction of the route can be organized as follows. Having received the field (/,у) for the beginning of the next route, set its number n= 1, put t 1 and t r each length p 64. Then proceed to identify the first valid field in the loop To. If such a field is found, enter the indices /, y into the arrays t ( t r meaning P = n + 1 - in and go to the beginning of the next cycle by To. If it is not found, change k = k + 1 and continue the cycle.

In the case where a valid field is not found, you should proceed to replace the resulting route with the best route and output the best route and its length. The block diagram of the route construction algorithm is shown in Fig. 1.46. Obviously, to store the best route, two arrays of indexes / and y are still needed - T P, t r length P

In conclusion, we present an enlarged text record of the algorithm for finding the best route for the knight.

Step 1. Initialize the board framing.

Step 2. Set / = -1.

Step 3. Set /, y.

Step 4. Initialize the board.

Step 5. Put P = 1, c1 (] = 1, k= 1.

Step 6. If /: > 8, go to step 10.

Step 7. Put / = / + / A, y = y + y*.

Step 8. If f o 0, put k = k+ 1 and return to step 6.

Step 9. Put i = P + 1, t 1= /, t y = y, To= 1 and return to step 6.

Step 10. If l > /, go to step 12.

Step 11. Replace the current route (t; , t^) for the best (t,„t m).

Step 12. Put /? = /?+ 1.

Step 13. If And 64, go back to step 3.

Step 14. Print the best route and its length /.

Step 15. Stop.

Problem 1.31. Let's consider another problem on a chessboard. You need to find all the options for placing eight rooks on the board so that they do not attack each other.

Anyone who plays chess knows that the rook beats any piece vertically and horizontally. Therefore, the rooks should not be located on the same vertical and horizontal. Two options for the arrangement of figures are shown in Fig. 1.47.

Rice. 1.47. Possible acceptable options for the placement of rooks on the board

In chess notation, the first option is written as a! b2 s3 64 e5 GB g7 И8, the second - like a 8 b 7 s 6 f e 4 T 3 g 2nd,. Of these

records it is easy to see that any admissible arrangement of rooks is determined by rearranging the first eight numbers of the natural series. Due to the fact that the number of permutations R p = 1 2 3 ... P= I!, in this case we will have P% = I x x2-3-4-5-6-7-8 = 8! = 40,320 possible options for placing rooks on the board. In order to obtain all these arrangements, it is necessary to construct an algorithm for constructing all permutations P numbers of the natural series. Several such algorithms are known. We will consider the simplest of them by constructing all permutations of the first three numbers of the natural series 1, 2, 3.

The idea of ​​the algorithm is to sequentially rotate the sequence of all specified numbers until all permutations are obtained. The rotation begins with the first permutation 123 and continues until the initial permutation is obtained. Thus, in this case we will have three permutations. Another reshuffle 123 1 will repeat the original permutation. To record this moment, it is necessary to constantly compare the number of rotated numbers (in this case 3) with the last number of the permutation and when they coincide, proceed to the next action of the algorithm. The next step is to check whether the number of numbers being rotated, in this case 3, is equal to two. If so, the entire number of permutations has been obtained. Otherwise, the number of numbers being rotated is reduced by one and the rotation continues, in this case the first two numbers. We get the permutation 213. We compare 2 with the last number of the permutation 3. They are not equal. We restore the number of rotated numbers to 3 and rotate the permutation 213. We get 132. We compare the number of rotated numbers 3 with the last number 2. They are still not equal. We rotate 132 and get 321. Further rotation of the permutation 321 gives 213, i.e., a permutation that was already obtained at the beginning of the second stage of rotations. We compare the number of rotated numbers 3 with two. They are not equal. We reduce the number of rotated numbers to two and rotate the first two numbers in the permutation 213. We get 123, compare the number of rotated numbers 2 with the last number of rotated numbers 2. They are equal. Next, we compare the number of rotated numbers 2 with two and finish constructing the permutations. All permutations have been constructed. They are listed below. Repeating permutations are enclosed in rectangles.

Let 1,2, ..., P - sequence of natural numbers; T - the number of rotated numbers in the permutation; To - the last number of the rotated permutation. Taking into account these notations, a block diagram of the algorithm for constructing all permutations P numbers of the natural series will be like this (Fig. 1.48).

In Fig. 1.49 shows fragments of the algorithm “to form a permutation 1, 2, ..., P" and “rotate the first T numbers in the last permutation", where R, -/"th number in the permutation.

Problem 1.32. Let's consider the following problem. On a closed interval [A, b a unimodal function is specified y =/(X), X e [a, b.

It is required to construct an algorithm for searching for point x* e [a, b, which delivers the greatest value to the function y*.

Before we begin solving this problem, recall that a function is unimodal if it is one-humped. Different kinds unimodal functions are presented in Fig. 1.50.

The fact that the unimodal function is one-humped allows, at two different points x 2, x 2 e [a, b] define interval a, b, to which x* belongs. Various variants of the relations /(x,) (x 2), /(x,) >/(x 2), /(x,) =/(x 2) highlight their subintervals [x, b], [a, x 2 ], [x, x 2 ], to which x* belongs. All of them are less than the original interval [a, b. For clarity, in Fig. 1.51 these subintervals are shaded.

Unimodality of function y=/(x) and the ability to calculate it at two points x, x 2 allow us to construct the following search procedure for x* with a certain error?. Let's take point x = (a + b)/ 2 dividing the interval [ A, b] in half. Let's move to the left

Rice. 1.48. Flowchart of the algorithm for constructing all permutations P numbers

natural series

Rice. 1.49.

from it and to the right at a distance e/2, i.e. we get points x, = = x- e/2, x 2 = x+ e/2, where e is the small distance between these points, equal to the accepted error in calculating x*. At points x 1? x 2 Let's calculate the values ​​of the function y, y 2. If, That X* is in the interval [x |) b. If y, >y 2, then X* is in the range [a, x 2. If y, = y 2, then point x is the value of x* found with an error of e. In this regard, we consider the procedure complete. Otherwise we set x, = A or x 2 = b and proceed to halving the interval [x, b] or [A, x 2 ] with further obtaining the points x, x 2 in the described way, calculating y, y 2, comparing them with each other and stopping in the case y x = y 2 or

continuation of further division. The process is completed when the interval is received

Note that after the first division we move on to the very

sparse interval length

Rice. 1.50. Unimodal functions:

A- convex; b- continuous non-smooth; V- unsmooth with breaks

final row

a - b e

• -- + - , after the second we go

to an interval of length

third division - to an interval of length

a-b (2 3 -1)7

A - b 3

• -+ - p.

a - b 3

• - + -Є

a - b | 7

• - + - 8 -

є. So after P in fact

of the original interval [ A, b] an interval of length will be obtained a-b (2"-1)

є. Where from given values a, b,є can-

but calculate the value P, showing how many divisions [a, b] must be executed to obtain the specified accuracy.

The block diagram of the algorithm that implements this procedure is shown in Fig. 1.51. The described method for finding the largest value

Enter a, b, c

X-X-e/2, X2=X+e/2

x*=x,y=f(x)

Output * * X ,y

Rice. 1.51. Block diagram of the algorithm for searching for the largest value of a unimodal

functions by half division method

unimodal function is known as the method of bisection, or dichotomy. There are, however, more effective methods solutions to this problem. These are the golden ratio and Fibonacci methods.

Let's consider the simplest of them - the golden section method.

According to this method, two values ​​of the function x, x 2 are first calculated, as in the dichotomy method. Then in the resulting subinterval [x, b] from the point x 2 to the right the value |x 2 - x, | and the value of the function is calculated at the point x 2 +|x 2 - x, |.

If, as a result of the first two calculations of the function at points x, x 2, an uncertainty interval is obtained [A, x 2 ], from point x, the value X[ - x 2 is plotted to the left and the function at point x is calculated, - | x, -x 2 |. The process continues until there is

the specified interval reduction accuracy has been achieved. It is shown schematically in Fig. 1.52.

Rice. 1.52.

golden ratio method

The method got its name from the method of dividing an interval, known since ancient times. a, b dot With into two unequal parts so that the ratio of the entire length of the interval to the length of the larger part is equal to the ratio of the length of the larger part to the length of the smaller part. In this case, the uncertainty interval [x, b] or [A, x 2 ] is divided by the point x, or x 2 in exactly this ratio.

Using the schematically described procedure, it is easy to construct an algorithm for calculating the largest value of a unimodal function, which will be proposed in paragraph “Problems for independent solution.”