Задание 1 ЕГЭ по информатике направлено на проверку умения представлять, считывать и анализировать данные в разных типах информационных моделей.
Про информационные модели мы уже говорили ранее. В задании 1 ЕГЭ нам предстоит работать с графами и таблицами. Граф в этих заданиях представляет собой упрощённую схему дорог между несколькими населёнными пунктами. Что же касается таблиц, точнее будет сказать матриц, то используются как матрицы смежности, так и весовые матрицы.
Как раз по этим матрицам мы и разделим задание 1 на два типа:
В заданиях первого типа нам даны граф и матрица смежности. Причём номера в матрице не совпадают с буквенными обозначениями на графе. Нужно понять, какой номер соответствует каждому населённому пункту, а затем записать номера указанных в условии пунктов.
В заданиях второго типа мы работаем с весовой матрицей и графом. Здесь номера в матрице тоже не совпадают с буквенными обозначениями на графе. Нужно верно их сопоставить, найти длины указанных дорог и обычно сложить полученные значения.
Решаются данные задания как ручным способом, так и программным. Как обычно, больше внимания уделим именно программному методу решения. Ну а статьи у нас будут разделены на две части, согласно типам этих заданий.
В этой статье мы познакомимся с первым типом задания 1, узнаем, как решать такие задания ручным методом и научимся применять, а главное — понимать, универсальный код, с помощью которого решается любое первое задание. Давайте приступать!
Алгоритм решения
Ручной метод
Как уже говорили, начнём с самого базового — ручного метода решения.
Рассмотрим такую формулировку:
На рисунке справа схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам B и E на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания
Итак, нужно проанализировать граф и сопоставить номера пунктов с их буквенными обозначениями на графе. Когда всё будет готово, нам останется лишь выписать две цифры, одна из которых соответствует пункту B, а вторая — E, и записать их в порядке возрастания.
Начинаем решение таких заданий с расстановки степеней вершин. Сделать это несложно: смотрим на вершину (точку с буквой) и далее считаем, сколько линий из неё выходит. Например, из вершины А у нас выходит 3 линии (отрезка/ребра): AC, AD, AG. Значит степень у вершины А будет 3. Аналогичным образом поступаем с оставшимися шестью вершинами. На рисунке степени обозначим оранжевым цветом.
В итоге видим, что у нас одна вершина D со степенью 5, одна вершина A со степенью 3 и все остальные вершины со степенью 2. Это следует запомнить: нам важно отметить все «необычные» вершины графа.
Теперь взглянем на матрицу смежности. Мы уже поняли, что самая «замечательная» вершина графа у нас D — ведь только она одна имеет степень 5. Как это отражается на матрице смежности? Всё просто, в соответствующем пункте (строке/столбце) будет пять «звёздочек».
Находим в матрице смежности строку (можно и столбец) с пятью звёздочками. Такой строкой является та, у которой номер 7.
Какой вывод можно сделать? Что вершине D соответствует пункт с номером 7 матрицы смежности. Чтобы не забыть, сразу отметим это в таблице. Здесь и далее у нас буквами будут называться столбцы, а цифрами — оставаться строки.
Аналогично поступим и с вершиной А, которая единственная имеет степень 3. Все так же: ищем строку с тремя «звёздочками» и подписываем соответствующий столбец.
Теперь можем найти номера вершин C и G. На деле мы не сможем однозначно определить, какой именно номер у выбранных вершин, поскольку тут граф симметричный и никаких признаков, отличающих эти две вершины у нас нет.
Единственное, что мы можем сказать, так это то, что у обеих вершин есть два соседа: A и D.
Смотрим по таблице, какие два столбца (из неизвестных) пересекаются с номерами 3 и 7. Это столбцы с номерами 1 и 4. Следовательно, у C и G номера 1 и 4 или наоборот.
Осталось всего три вершины. Что можем сказать на данный момент:
Каждая из вершин B и E соединена с одной известной (D) и одной неизвестной (F)
Вершина F — единственная, которая не соединена с уже известными вершинами
Давайте тогда определим номер для вершины F. Задача простая: нужно найти в таблице строку, которая не имеет «звёздочек» в уже известных столбцах (C, A, G, D), при этом в ней ровно две звёздочки.
Как видим, такой строкой является пятая. Значит, отметим, что у пункта F будет номер 5.
Ну а оставшиеся две вершины должны соединяться с D и F, то есть иметь «звёздочки» в указанных столбцах.
Да, как ни удивительно, но со столбцами D и F пересекаются как раз оставшиеся две строки — 2 и 6. Под этими номерами и будут вершины B и E.
В ответ даём два этих номера в порядке возрастания: 26.
Программный метод
Ручной метод хорош, но порой бывают сложные или неудобные для анализа графы. Например, как в следующем задании:
На рисунке изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера в таблице могут соответствовать населённым пунктам B и C на схеме.
В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Тут у нас и граф симметричный, и несколько вершин со степенями 2 и 3. Нужно анализировать не только соседние вершины, но и соседей этих соседей. Это может занять много времени. В конце концов, гораздо проще иметь под рукой шаблонное решение, правда?
Давайте как раз и выведем такой код. Давайте подумаем, а что мы делали при ручном решении?
При ручном решении мы искали какую-то «особенную» точку: например, вершину с уникальной степенью. Так удавалось сразу найти зависимость и определить подходящий номер для пункта.
Но как бы нам следовало поступить, будь у нас куда больше времени, но меньше «интуиции», которая бы нам подсказывала? Скорее всего мы бы просто «выстреливали» предположениями: «Пусть А=1, B=2, C=3 и т.д.» и проверяли, сходится ли матрица с графом. Если нет, то переставляли бы номера и проверяли снова и так, пока не наткнёмся на верное соотношение номеров и букв.
Так давайте заставим компьютер переставлять все возможные значения пунктов до тех пор, пока не будет найдено подходящее! Начнём писать наш код.
Здесь не просто так несколько раз прозвучало слово «перестановки». Именно их мы будем использовать в коде. А реализует перестановки функция permutations из модуля itertools — импортируем её.
from itertools import permutations
Далее нам нужно переписать все рёбра графа. То есть буквально выбираем любую точку и от неё идём по часовой стрелке, против часовой стрелки или по диагонали — неважно. Главное выписать все рёбра! Здесь 9 рёбер (дорог) и запишем их в виде строки, которую разделим на части по пробельному символу. Таким образом получим список строк graph:
from itertools import permutations
graph = 'CG GF FB BD DA AE EC GE FD'.split()
Теперь запишем таблицу из условия. Как это сделать: смотрим на каждую строку по очереди. Выписываем номера тех столбцов, под которыми стоит «звёздочка» в этой строке. Например, в строке 1 «звёздочки» стоят под столбцами 2, 3 и 4. Это означает, что из пункта 1 есть дороги в пункты 2, 3 и 4.
Записывать их будем аналогично с рёбрами: в одну строку, которую разделим через split():
from itertools import permutations
graph = 'CG GF FB BD DA AE EC GE FD'.split()
matrix = '234 136 12 157 467 25 45'.split()
В переменной matrix у нас такой список:
['234', '136', '12', '157', '467', '25', '45']
То есть первый элемент этого списка — matrix[0] — это строка 234, второй — 136. Иными словами, каждый элемент списка означает, в какие пункты из него есть дороги.
Можем приступать к перебору всех возможных перестановок вершин. Делать это, конечно же, будем в цикле for:
from itertools import permutations
graph = 'CG GF FB BD DA AE EC GE FD'.split()
matrix = '234 136 12 157 467 25 45'.split()
for i in permutations('ABCDEFG'):
Именно permutations создаёт перестановки всех вершин нашего графа, например, так:
('F', 'D', 'B', 'G', 'E', 'A', 'C')
Это означает, что вершине F соответствует номер 1 из матрицы смежности, D — 2 и так далее.
Кортеж читаем слева направо: первая буква соответствует пункту 1, вторая — пункту 2 и так далее. Но индексы в программе начинаются с нуля. Поэтому у буквы F индекс 0, хотя её номер в матрице — 1. Чтобы получить номер вершины, к индексу нужно добавить единицу.
Теперь нужно написать самую страшную и сложную строку, которая как раз и будет проверять соответствие рёбер и вершин. Выглядит она так:
from itertools import permutations
graph = 'CG GF FB BD DA AE EC GE FD'.split()
matrix = '234 136 12 157 467 25 45'.split()
for i in permutations('ABCDEFG'):
if all(str(i.index(x) + 1) in matrix[i.index(y)] for x, y in graph):
Разберём её по частям. Начнём с цикла for x, y in graph. Здесь в каждую переменную передаётся по одной букве ребра из списка graph.
CG → x=’C’, y=’G’
GF → x=’G’, y=’F’
FB → x=’F’, y=’B’ и так далее.
Далее эта часть: i.index(x) + 1. Здесь мы получаем позицию буквы из текущей перестановки. В первой итерации цикла у нас x имеет значение «С». А первая перестановка (i) такая: ('F', 'D', 'B', 'G', 'E', 'A', 'C'). Следовательно запись i.index(x) + 1 возвращает номер буквы С — 7.
Аналогично сработает и с записью i.index(y) + 1 — получим номер буквы G (y=’G’) в текущей перестановке, то есть число 4. Функцией str() мы превращаем это число в строку.
И теперь идёт проверка: str(i.index(x) + 1) in matrix[i.index(y)]. Сначала берём строку матрицы, соответствующую вершине y. Затем проверяем, есть ли среди её соседей номер вершины x. Проще говоря: существует ли в матрице дорога, которую мы выписали с графа.
Давайте прямо подставим известные нам значения. Иными словами проверяется, есть ли число 7 в четвёртом элементе списка matrix (то есть в четвёртой строке матрицы смежности) — в '157'.
Как мы видим, в строке '157' действительно есть цифра 7, значит проверка пройдена. То есть пункт 4 связан дорогой с пунктом 7, и это дорога «GC».
Но функция all()в записи all(str(i.index(x) + 1) in matrix[i.index(y)] for x, y in graph) требует, чтобы для всех перебираемых в цикле значений «x, y» выполнялась эта проверка. Если это действительно так, то условие становится истинным, значит можно вывести на экран текущую перестановку (переменную i):
print(i)
В итоге весь код у нас выглядит так:
from itertools import permutations
graph = 'CG GF FB BD DA AE EC GE FD'.split()
matrix = '234 136 12 157 467 25 45'.split()
for i in permutations('ABCDEFG'):
if all(str(i.index(x) + 1) in matrix[i.index(y)] for x, y in graph):
print(i)
К счастью, у нас первый вариант — граф действительно симметричный, и об этом мы сказали ещё в самом начале.
В задании от нас требовалось найти номера пунктов B и C. В обоих кортежах им соответствуют номера 3 и 7, только в разном порядке. Поэтому ответ однозначный: 37.
Пример
Решим ещё одно задание программным методом. Формулировка будет такой:
На рисунке изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера в таблице могут соответствовать населённым пунктам D и Е на схеме.
В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Импортируем нужную функцию, перепишем все рёбра и номера вершин из матрицы:
from itertools import permutations
graph = 'GA GF GE GD GC GB AF FE ED DC CB'.split()
matrix = '345 467 34 123567 147 24 245'.split()
Запустим цикл и проверку условия:
from itertools import permutations
graph = 'GA GF GE GD GC GB AF FE ED DC CB'.split()
matrix = '345 467 34 123567 147 24 245'.split()
for i in permutations('ABCDEFG'):
if all(str(i.index(x) + 1) in matrix[i.index(y)] for x, y in graph):
И теперь давайте не вручную искать нужные номера для пунктов D и Е, а сразу из текущей перестановки (i) получим номера этих вершин через метод index() и отсортируем эти номера в порядке возрастания функцией sorted().
Таким образом на экране мы сразу увидим нужные для ответа значения.
Вся программа будет выглядеть так:
from itertools import permutations
graph = 'GA GF GE GD GC GB AF FE ED DC CB'.split()
matrix = '345 467 34 123567 147 24 245'.split()
for i in permutations('ABCDEFG'):
if all(str(i.index(x) + 1) in matrix[i.index(y)] for x, y in graph):
print(*sorted((i.index("D") + 1, i.index("E") + 1)))
А выведет она числа 5 и 7, которые и запишем в ответ.
Перед запуском кода обязательно ещё раз проверьте, что выписали каждое ребро ровно один раз и не пропустили ни одной связи в матрице. Большинство ошибок в программном методе появляется именно при переносе данных из условия.
На этом мы закончим разбор первого типа задания 1 ЕГЭ по информатике. А в следующей статье уже познакомимся со вторым типом, научимся работать с весовой матрицей и также решим задания двумя методами: ручным и программным.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
