1 задание ЕГЭ информатика
Граф и таблица (информационные модели)
1 балл ≈ 3 мин уровень Б Чтение данных в информационных моделях (граф, таблица)
Задание 1 – схема дорог дана дважды: графом с буквами и таблицей с номерами, нумерация не совпадает. Нужно сопоставить вершины и найти длину дороги (или сумму длин). 1 балл. Компьютер не нужен.
Алгоритм
- Посчитай степень (число дорог) каждой вершины графа: A – 3, B – 2 и т. д.
- Посчитай степень каждого номера в таблице: число заполненных клеток в строке.
- Вершины с уникальной степенью сопоставляются сразу. Остальные различай по соседям: «вершина степени 3, соседняя с единственной вершиной степени 4».
- Когда нужные буквы сопоставлены с номерами, прочитай длину дороги на пересечении строки и столбца таблицы.
Разобранный пример. В графе: A–B, A–C, A–D, B–C, D–E. Степени: A – 3, B – 2, C – 2, D – 2, E – 1. В таблице: П1 связан с П3 (7), П1 – П4 (5), П1 – П5 (9), П3 – П5 (4), П4 – П2 (6). Степени: П1 – 3, П2 – 1, П3 – 2, П4 – 2, П5 – 2. Значит, A = П1, E = П2. D – сосед E, значит D = П4. Найди длину дороги A–D: П1–П4 = 5.
| П1 | П2 | П3 | П4 | П5 | |
|---|---|---|---|---|---|
| П1 | 7 | 5 | 9 | ||
| П2 | 6 | ||||
| П3 | 7 | 4 | |||
| П4 | 5 | 6 | |||
| П5 | 9 | 4 |
Ловушки: симметричные вершины (одинаковые степени и одинаковые соседи) различить нельзя, но условие обычно спрашивает о такой дороге, где это неважно; таблица симметрична – считай степень по одной строке, а не по строке и столбцу вместе.
- Выпиши степени вершин графа и номеров таблицы в две строки рядом – соответствие видно сразу.
- Начинай сопоставление с уникальных степеней, затем двигайся по соседям.
- Если спрашивают сумму двух дорог – сопоставь все четыре вершины, а не только одну пару.
Разобранные задания 1 из открытого банка ФИПИ
Пример 1 · код ФИПИ 2B8787
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| Номер пункта |
| |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Номер пункта | 1 | 13 | 5 | |||||||
| 2 | 21 | 39 | 8 | |||||||
| 3 | 21 | 53 | ||||||||
| 4 | 2 | 3 | ||||||||
| 5 | 13 | 1 | ||||||||
| 6 | 5 | 53 | 2 | |||||||
| 7 | 39 | 1 | 30 | |||||||
| 8 | 8 | 3 | 30 | |||||||
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана
с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта B в пункт C
и из пункта G в пункт H.
В ответе запишите целое число.
Показать ответ и решение
Ответ: 21
Сопоставляем степени вершин графа и строк таблицы (число заполненных клеток), затем однозначно восстанавливаем соответствие пунктов .
Перебор всех соответствий (программа) даёт: BC = 8, GH = 13, сумма 21. Ответ: 21.
Пример 2 · код ФИПИ 656B8A
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| Номер пункта |
| ||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |||
| Номер пункта | 1 | 8 | 21 | ||||||
| 2 | 8 | 5 | 30 | ||||||
| 3 | 13 | 53 | |||||||
| 4 | 5 | 13 | 3 | ||||||
| 5 | 53 | 2 | 39 | ||||||
| 6 | 30 | 3 | 2 | ||||||
| 7 | 21 | 39 | |||||||
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак
не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта F в пункт B и из пункта E в пункт C.
В ответе запишите целое число.
Показать ответ и решение
Ответ: 74
Однозначное соответствие по степеням и соседству: A=6, B=5, C=1, D=2, E=7, F=3, G=4.
F–B = П3–П5 = 53, E–C = П7–П1 = 21; сумма 74.
Пример 3 · код ФИПИ 9D1C5D
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак
не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта А
в пункты В и Е.
В ответе запишите целое число.
Показать ответ и решение
Ответ: 13
А – единственная вершина степени 6 (П2). Цепочка Б–В–Г–Д–Е–К соответствует 1–3–5–7–6–4 (или обратно).
А–В + А–Е = П2–П3 + П2–П6 = 5 + 8 = 13.
Частые вопросы о задании 1
Сколько баллов даёт задание 1 ЕГЭ по информатике?
Максимум – 1 первичный балл. Норма времени на экзамене – около 3 мин. Уровень сложности – Б.
Что проверяет задание 1?
Задание 1 – схема дорог дана дважды: графом с буквами и таблицей с номерами, нумерация не совпадает. Нужно сопоставить вершины и найти длину дороги (или сумму длин). 1 балл. Компьютер не нужен.
Как подготовиться к заданию 1?
Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.