Another task example. Another example of a task Roads built between settlements abcde length
I present the solution of task 3 of the OGE-2016 in informatics from the demo project. Compared to the 2015 demo, task 3 has not changed. This is a task for the ability to analyze formal descriptions of real objects and processes (formalization of the description of real objects and processes, modeling of objects and processes).
Screenshot of 3 tasks.
Exercise:
3. Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is given in the table.
Determine the length of the shortest path between points A and E. You can only move along the roads, the length of which is indicated in the table.
1) 4
2) 5
3) 6
4) 7
Based on the table given in the task, we build a graph. From point A you can get to points B, C and D, and from them - to C, D, E, etc. Do not forget that we need to go to point E (some options can be immediately discarded, because the road to point E will be unequivocally long). Then we calculate the length of the path for each route and choose the smallest of them.
ABCE=2+1+2=5
ACE=5+2=7
ADCE=1+3+2=6
In our case, this is the route ABSE (2+1+2=5).
This type of task is found at number 3 in the text of the OGE in computer science.
Example 1
Roads were built between settlements A, B, C, D, E, F, the length of which is shown in the table. (The absence of a number in the table means that there is no direct road between the points.)
Determine the length of the shortest path between points A and F (assuming that you can only move along the constructed roads).
Solution:
1. Let's build a graph - a scheme corresponding to this weight matrix; from vertex A you can go to vertices B and C (path lengths are 2 and 4, respectively):
2. For other vertices, only the part of the table above the main diagonal, which is highlighted in gray, can be considered; all other edges have already been considered earlier
4. New routes from C to D and E (path lengths 3 and 4, respectively):
5. New route from D - to E (path length 3):
6. New route from E to F (path length 2):
7. You need to go from A to F, according to the scheme, we see that any of these routes includes an edge EF of length 2; thus, it remains to find the optimal route from A to E
8. Let's try to list possible routes from A to E:
- A - B - E length 9
- A - B - C - E length 7
- A - B - C - D - E length 9
- A -C - E length 8
- A -C - B - E length 12
- A -C - D - E length 10
9. Of the listed routes, the shortest - A-B-C-E - has length 7, so the total length of the shortest route A-B-C-E-F is 7 + 2 = 9
10. So the correct answer is 9.
Example 2
Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is shown in the table.
Determine the length of the shortest path between points A and E. You can only move along the roads, the length of which is indicated in the table.
1) 4
2) 5
3) 6
4) 7
Solution:
1. Let's build a graph - a scheme corresponding to this weight matrix; from vertex A you can go to vertices B, C and D (path lengths are 2, 5 and 1, respectively)
2. For other vertices, only the part of the table above the main diagonal, which is highlighted in gray, can be considered; all other edges have already been considered earlier. For example, BA=AB=2. If the lower part of the table differs from the upper one, then we build a separate route. In tasks, as a rule, the table is symmetrical.
3. From vertex B you can go to vertex C (path length 1): 
4. From vertex C you can go to vertices D, E (path lengths 3 and 2):
5. You need to go from A to E, according to the scheme we see that any of these routes includes an edge CE of length 2; thus, it remains to find the optimal route from A to C
Let's try to compose all possible route options from point A to point C:
A-C = 5
A-B-C = 3
A-D-C = 4
It can be seen that the shortest route from A to C is the route A-B-C. Adding the last edge C-E, we get the length of the route A-B-C-E = 3 + 2 = 5. This is the second answer.
Answer: 2
R-05.One-way roads have been built between settlements A, B, C, D, E, F, Z. The table shows the length of each road. The absence of a number in the table means that there is no direct road between the points. For example, there is a 4 km road from A to B, but there is no road from B to A.
How many such routes from A to Z are there that pass through 6 or more settlements? Points A and Z should be taken into account when calculating. You cannot go through the same point twice.
Solution (1 way, enumeration of options):
we are not interested in the AZ route, although it arrived at the final destination, it passes through less than 6 points (only 2!); hereinafter such "uninteresting" routes from A to Z will be highlighted with a gray background
now we are looking for all routes passing through 3 points; from B you can only go to C, and from C you can only go to D and Z:
-
we build the next level only for those routes that have not yet reached Z:
The next two levels give "interesting" routes passing through 6 or 7 points:
note that the numbers in the table do not interest us at all - it is enough to know that there is a road between these points
we need to find all paths that pass through 6 or more points, counting the start and end points; i.e. there must be at least 4 waypoints between A and Z
start by listing all routes from A that pass through 2 points; according to the table, we see that from A you can go to B, C and Z; the number of points on the route will be written from above:
it was possible to draw a diagram of possible routes in the form of a tree:
on the last diagram, “interesting” routes are highlighted with a green background, there are only 6 of them; the red background marks the routes in which the cycle turned out - they pass through the same point twice; such routes are prohibited and we do not consider them further
Solution (method 2, through the construction of a graph, M.V. Kuznetsova)
The total number of points is 7. There are roads connecting all 7 points in series, so the 1st path is ABCDEFZ.
There are 3 roads that allow you to “pass past” the neighboring point (AC goes “past” B, DF - past E, ...), so there are 3 ways to pass through 6 points ( AC DEFZ,ABC D.F. Z,ABCD EZ).
…
There is one "reverse road" that allows you to change the order of passing points - FE. This road, in the presence of road DF, going "past" E, creates additional routes: one through 7 pointsABC DFE Z and one after 6 points ACDFE Z.
Conclusion: total number of roads matching the condition: 1+3+2=6
Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is shown in the table.
Determine the length of the shortest path between points A and E. You can only move along the roads, the length of which is indicated in the table.
SOLUTION
Thus, we draw the remaining points, discarding repeating segments. For example, segment AB=2 and segment BA=2 are the same, so we do not write BA. After the scheme is ready, it is necessary to write out all possible options for the resulting segments. The segments must necessarily begin with A and end with E, as required by the condition of the problem. It is most convenient to write out the segments in the form of a table (see figure). As you can see from the table, we got 3 segments: ABCE = 5, ACE=7 and ADCE = 6. In the task, you need to determine the length the shortest path between points A and E. The shortest path is the minimum number of resulting segments. This requirement corresponds to the number 5, and this is the 2nd answer option.
Answer: 2
To get a head start in IT and make the most of your study time, choosing the right one is essential.
Independent work
In the figure on the right, the road map of the N-sky district is shown as a graph; the table on the left contains information about the length of each of these roads (in kilometers).
Since the table and the diagram were drawn independently of each other, the numbering of settlements in the table is in no way connected with the letter designations on the graph. Determine the length of the road from point B to point C. In your answer, write down an integer - as it is indicated in the table.
Write your answer in the comments of this post.
Size: px
Start impression from page:
transcript
1 Task 3. Formal descriptions of real objects and processes 3.1. Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 5 2) 6 3) 7 4) Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 7 2) 8 3) 9 4) Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 9 2) 10 3) 11 4) Between settlements A, B, C, D, E built roads, the length of which (in kilometers) is given 1) 5 2) 6 3) 7 4) Roads were built between settlements A, B, C, D, E, the length of which ( in kilometers) is given
2 1) 8 2) 9 3) 10 4) Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 9 2) 10 3) 11 4) Between settlements A, B, C, D, E roads are built, the length of which (in kilometers) is given 1) 9 2) 8 3) 7 4) Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 4 2) 5 3) 6 4) Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 6 2) 7 3) 8 4) Between settlements A, B , C, D, E roads are built, the length of which (in kilometers) is given
3 1) 5 2) 6 3) 7 4) Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 6 2) 7 3) 8 4) Between settlements A, B, C, D, E roads are built, the length of which (in kilometers) is given 1) 6 2) 7 3) 8 4) Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 6 2) 7 3) 8 4) Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 4 2) 5 3) 6 4) Between settlements A, B , C, D, E roads are built, the length of which (in kilometers) is given
4 1) 7 2) 8 3) 9 4) Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 13 2) 12 3) 11 4) Between settlements A, Roads B, C, D, E are built, the length of which (in kilometers) is given Determine the length of the shortest path between points A and F. You can only move along roads, the length is 1) 9 2) 11 3) 13 4) Between settlements A, Roads B, C, D, E are built, the length of which (in kilometers) is given Determine the length of the shortest path between points A and F. You can only move along roads, the length is 1) 5 2) 6 3) 7 4) Between settlements A, B, C, D, E, F roads are built, the length of which is given Determine the length of the shortest path between points A and F. You can only move along roads, the length
5 1) 5 2) 6 3) 7 4) Roads were built between settlements A, B, C, D, E, F, the length of which (in kilometers) is given Determine the length of the shortest path between points A and F. You can only move along roads, length 1) 5 2) 6 3) 7 4) Roads were built between settlements A, B, C, D, E, F, the length of which is given Determine the length of the shortest path between points A and F. You can only move along roads, length 1) 5 2) 6 3) 7 4) Roads were built between settlements A, B, C, D, E, F, the length of which is given Determine the length of the shortest path between points A and F. You can only move along roads, length 1 ) 6 2) 7 3) 8 4) Roads were built between settlements A, B, C, D, E, F, the length of which is given
6 Determine the length of the shortest path between points A and F. You can only move along roads, the length of 1) 6 2) 7 3) 8 4) Roads were built between settlements A, B, C, D, E, F, the length of which is given Determine the length of the shortest path between points A and F (assuming that you can only move along the constructed roads). 1) 5 2) 6 3) 3 4) Task Roads were built between settlements A, B, C, D, E, F, the length of which is given Determine the length of the shortest path between points A and F (provided that you can only move along built roads). 1) 5 2) 6 3) 7 4) Roads are built between settlements A, B, C, D, E, F, the length of which is given Determine the length of the shortest path between points A and F (provided that you can only move along the constructed roads).
7 1) 5 2) 7 3) 3 4) Roads were built between settlements A, B, C, D, E, F, the length of which is given Determine the length of the shortest path between points A and F (provided that you can only move along constructed roads). 1) 6 2) 8 3) 10 4) Ivan Tsarevich hurries to rescue Marya Tsarevna from the captivity of Koshchei. The table shows the length of the roads between the points through which he can pass. Indicate the length of the longest section of the shortest path from Ivan Tsarevich to Marya Tsarevna (from point I to point M). You can only move along the roads indicated 1) 1 2) 2 3) 3 4) Ivan Tsarevich hurries to rescue Marya Tsarevna from Koshchei's captivity. The table shows the length of the roads between the points through which he can pass. Indicate the length of the shortest section of the shortest path from Ivan Tsarevich to Marya Tsarevna (from point I to point M). You can only move along the roads indicated 1) 1 2) 2 3) 3 4) Petya Ivanov's relatives live in 5 different cities of Russia. The distances between cities are included in the table: Petya redrawn it in a notebook in the form of a graph. Assuming that the boy did not make a mistake when copying, indicate which count Petya has in his notebook.
8 1) 2) 3) 4) Katya Yevtushenko has relatives living in 5 different cities of Russia. Distances between cities are included in the table: Katya redrawn it in a notebook in the form of a graph. Assuming that the girl did not make a mistake when copying, indicate which graph Katya has in her notebook. 1) 2) 3) 4) Teacher Ivan Petrovich lives at Antonovka station, and works at Druzhba station. In order to be in time for lessons in the morning, he must take the shortest road. Analyze the table and indicate the length of the shortest path from Antonovka station to Druzhba station: 1) 6 2) 2 3) 8 4) Teacher Marya Petrovna lives at Vasilki station, and works at Druzhba station. In order to be in time for lessons in the morning, she must take the shortest road. Analyze the table and indicate the length of the shortest path from Vasilki station to Druzhba station: 1) 5 2) 6 3) 8 4) The rural ungraded school is located in the village of Ivanovskoye. Kolya Ivanov lives in the village of Vershki. Determine the minimum distance he needs to walk to get to school:
9 1) 6 2) 9 3) 12 4) The rural ungraded school is located in the village of Vershki. Roma Orlov lives in the village of Dalnee. Determine the minimum distance he needs to walk to get to school: 1) 6 2) 8 3) 11 4) Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is given 1) 4 2) 5 3) 6 4) The car driver must get from point A to point D in 5 hours. From the presented tables, select the one according to which the driver will be able to get from point A to point D in this time. The cells of the table indicate the time (in hours) it takes to get from one point to another. You can only travel on the roads indicated in the tables. 1) 1 2) 2 3) 3 4) The car driver must get from point A to point C in 6 hours. From the presented tables, select the one according to which the driver will be able to get from point A to point C in this time. The cells of the table indicate the time (in hours) it takes to get from one point to another. You can only travel on the roads indicated in the tables.
10 1) 1 2) 2 3) 3 4) Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is given Determine the length of the shortest path between points A and B. You can only move along roads, length 1) 4 2) 6 3) 10 4) Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) is given Determine the length of the shortest path between points A and B. You can only move along roads, length 1) 1 2) 5 3) 3 4) Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is given Determine the length of the shortest path between points A and B (provided that it is possible to move only on built roads). 1) 11 2) 12 3) 13 4) Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is given Determine the length of the shortest path between points A and C (provided that you can only move built roads).
11 1) 6 2) 7 3) 8 4) Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is given Determine the length of the shortest path between points A and D. You can only move along roads, length 1) 5 2) 6 3) 7 4) Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is given Determine the length of the shortest path between points A and E. You can only move along roads, length 1) 4 2) 6 3) 8 4) Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is given Determine the length of the shortest path between points A and C. You can only move along roads, length 1) 3 2) 5 3) 8 4) Roads were built between settlements A, B, C, D, E, the length of which (in km) is given in the table. Determine the length of the shortest path between points A and C. You can only move along roads, the length is 1) 7 2) 8 3) 9 4) The driver of the electric train must get from point A to point C in 6 hours. From the presented tables, select the one according to which the driver will be able to get from point A to point C in this time. The cells of the table indicate the time (in hours) it takes to get from one point to another. You can only travel on the roads indicated in the tables.
12 3.48. The train driver must get from point A to point C in 4 hours. From the presented tables, select the one according to which the driver will be able to get from point A to point C in this time. The cells of the table indicate the time (in hours) it takes to get from one point to another. You can travel only on the roads indicated in the tables The table shows the cost of transportation between the five railway stations, marked with the letters A, B, C, D and E. Indicate the scheme that corresponds to the table.
13 3.50. The table shows the cost of transportation between five railway stations, labeled A, B, C, D, and E. Indicate the scheme that corresponds to the table.
Unified State Examination in Informatics Tasks KIM 3 Section 97: OGE: Finding the optimal path in the graph Section 117: OGE: Determining the scheme corresponding to the table (graph weight matrix). Total tasks: 22 3 (638) Teacher
Tasks 3. Formal descriptions of real objects and processes 1. A 1 B 1 2 2 7 C 2 3 D 2 4 E 7 3 4 which is indicated in 2. 4) 8 3. 1) 7 2) 8 3) 9 4) 10 4. 1) 9 2) 10 3) 11 4) 12 2019-04-28 1/20 5. 6. 1) 8
Tasks 3. Formal descriptions of real objects and processes 1. Task 3 3. Roads were built between settlements A, B, C, D, E, the length of which (in kilometers) A B C D E A 1 B 1 2 2 7 C
Tasks 3. Formal descriptions of real objects and processes 1. kilometers) is given in the table: A B C D E A 1 B 1 2 2 7 C 2 3 D 2 4 E 7 3 4 roads, the length of which is indicated in the table. 3) 7 4) 8
Tasks A3. Formal descriptions of real objects and processes
Option 1 1. Roads are built between settlements A, B, C, D, E, the length of which (in kilometers) is shown in the table. Determine the length of the shortest path between points A and E. You can move
Exercise. Information modeling (basic level, time min) Tasks for self-solving :) The diagram shows roads between five cities, and the lengths of the roads are indicated. Define,
Option 15 1. To receive a yearly grade in history, the student was required to write a report of 16 pages. Performing this task on a computer, he typed text in Windows encoding. How much memory (in
Starting control grade 10 Option 1 (Tasks 1-12 for 1 point) Part 1 (circle the number of the correct answer) 1. The editor-in-chief of the journal edited the article, and its volume was reduced by two pages. Each
Information Models What you need to know: It is useful to know what a graph is (it is a set of vertices and edges connecting them) and how it is described in the form of a table, although, as a rule, all the necessary explanations are given in
Demo version Informatics, Grade 9 TASK A. A1. The article typed on a computer contains 16 pages, each page has 32 lines, each line has 25 characters. Determine the information volume
The equation of motion. Uniform movement. 1. At 4 p.m., a train passenger drove past a kilometer post on which 1456 km was written, and at 7 a.m. the next day past a post with the inscription
10. Information processing 10.1 Processed objects: strings of symbols, numbers, lists, trees. Tasks of the GIA 1. (2009) The table shows the cost of transportation between five railway stations, indicated
Option 20 1 (592) In one of the editions of M.A. Bulgakov "Master and Margarita" 256 pages. What amount of memory (in MB) would this book take if Mikhail Afanasyevich typed it on a computer and saved
Tasks for movement towards and in opposite directions. Purpose: to form the ability to solve problems of this type. 1. Organizational moment. 2. Oral work. Calculate: The course of the lesson. a) 170+180; b) 330-90;
3. Analysis of information models Demonstration version of the USE 2018 task 3 In the figure on the right, the road map of the N-sky district is shown as a graph, the table contains information about the length of each
Option 1 1. The abstract typed on the computer contains 16 pages, each page has 50 lines, each line has 64 characters. Characters are encoded using the Unicode encoding, in which each
Demonstration version of the entrance test in grade 9 Task 1 To obtain an annual grade for the MHC, the student was required to write a report on 8 pages. While doing this task on the computer, he typed
Option 18 1 (590) To receive an annual grade in history, the student was required to write a report of 16 pages. Performing this task on a computer, he typed text in Windows encoding. What is the amount of memory
K. Polyakov, 009-06 (basic level, time min) Topic: Using information models (tables, diagrams, graphs). Enumeration of options, choosing the best for some reason. What you need to know: Basically,
OGE option 19 1 In one of the editions of the book by L.N. Tolstoy "War and Peace" 1024 pages. What amount of memory (in MB) would this book take if Lev Nikolaevich typed it on a computer in KOI-8 encoding?
MATHEMATICS, class, EMC 1 Option 1, May 2012 (EMC secondary school of the city (district), class OPTION 1 minutes. 1. When performing 1 - tasks, only answers must be indicated. When MATHEMATICS, class, EMC 1 Option 1, May 2012 2. From
Option 203243 1. B 3 404. Roads were built between settlements C, D, E, F, the length of which is given in the table: Determine the length of the shortest path between points and F. You can move
MATHEMATICS, grade 4 Option 1, April 2012 Secondary School of the city (district), grade 4 OPTION 1 1. Sixty thousand fifteen is ... 1) 60015 2) 6015 3) 6000015 4) 615 April 2012 2. Complete
Checking work in MATHEMATICS 5 CLASS Option 12 Instructions for performing work 60 minutes are given to complete the work in mathematics. The work contains 14 tasks. In tasks, after which there is a field with
Option 19. 1 (591) In one of the editions of L.H. Tolstoy "War and Peace" 1024 pages. What amount of memory (in MB) would this book take if Lev Nikolaevich typed it on a computer in encoding
Math testing. 6th grade. 2011 Option 1 Group A 1. Solve the equation: 8 x \u003d 3 A. 4 2 9 B. 2 C. 4 2 9 D. 3 2. Find the value of the expression 3 2 A. B. C. D. 3. Which of the numbers is greater 1 but less
OGE Grade 9 Task #1 The story typed on the computer contains 2 pages, each page has 24 lines, each line has 64 characters. Determine the information volume of the story in Kbytes in KOI8-R encoding,
Attention! The Moscow Methodological Commission for Informatics organizes seminars to prepare for the Olympiads. Schoolchildren of 7-8 grades are invited, who have become winners and prize-winners of the district stage of the All-Russian
Lesson 1 Speed. Time. Distance 1 Misha skied a distance of 8 m in 2 s, and Igor 45 m in 15 s. Which of them traveled a greater distance, and who less Who walked more time, and who less Who walked faster,
Topic: Using information models (tables, charts, graphs). Enumeration of options, choosing the best for some reason. What you need to know: in principle, special additional knowledge, except for common sense
Diagnostic work 1. Option 0011 (without logarithms) October 3, 008 Instructions for performing the work 90 minutes are given to complete the work. The work contains 11 tasks (1B 9B, 10C, 11C). In tasks 1B
Speed. Time. Distance LESSON Task. Misha skied a distance of 80 m in 0 s, and Igor 45 m in 5 s. Which one was faster? (By distance we mean the length of the road connecting the beginning and
Variant 718051 1. Task 3 624. Teacher Ivan Petrovich lives at Antonovka station, and works at Druzhba station. In order to be in time for lessons in the morning, he must take the shortest road. Analyze
Spreadsheet Materials for the site on informatics Grade 9 (immersion 2) Teachers: Alexandrova T.A. Topic Know Be able Job bank What is a spreadsheet, the main parameters of spreadsheets,
Mathematics Movement problems 1. Write down only the answers in the problems. a) A camel travels 35 km every hour. How fast is he going? b) A bee flies 6 m every second. What is the bee's speed? c)
Task 1. Alphabet Quite recently, Lyosha began to study English at school. As often happens, in some aspects of the study of this subject he reached unsurpassed heights, while in others, on the contrary, he faced
K. Polyakov, 009 0 (basic level, time min) Topic: Using information models (tables, diagrams, graphs). Enumeration of options, choosing the best for some reason. What you need to know: Basically,
To make chains, beads marked with letters: A, B, C, are used. In the first place in the chain is one of the beads A, C,. On the second, any vowel if the first letter is a vowel, and any consonant if
Movement schedules 1. At the physical education lesson, Petya and Masha ran together along a straight path, starting from the school. Then Petya ran faster, and Masha went. After a while, the guys turned back at the same time
The scientist Ivanov leaves Moscow for a conference at St. Petersburg University. The conference starts at 10:00. The table shows the schedule of night trains from Moscow to Saint Petersburg. train number
Option 1 1. The student during the week wrote down the time he spends preparing lessons: Day of the week Mon Tue Wed Thu Fri Time (in minutes) 120 80 100 90 110
0 Topic: Using information models (tables, charts, graphs). Enumeration of options, choosing the best for some reason. What you need to know: in principle, special additional knowledge, except for common sense
«How to get to us» By car From Odessa Drive along the Odessa-Nikolaev highway for about 45 km to the CENTER of Koblevo village. We pay attention to 2 significant points: 1. You need to get to
7m7 Speed. Time. Distance Tutorial L.G. Peterson, III class L.V. SELKINA, Candidate of Pedagogical Sciences, Associate Professor D.I. TARASOVA, student, Perm State Pedagogical University Goals:
Checking work in MATHEMATICS 5 CLASS Option 13 Instructions for performing work 60 minutes are given to complete the work in mathematics. The work contains 14 tasks. In tasks, after which there is a field with
Sheet 2 DEPARTMENT OF INDUSTRY AND TRANSPORT OF THE VORONEZH REGION (full name of the carrier) "APPROVED" (authorized official) MP (signature) (full name) 20 PASSPORT of the intermunicipal bus
(basic level, time min) Topic: Use of information models (tables, charts, graphs). Enumeration of options, choosing the best for some reason. What you need to know: in principle, special additional
Loading...