О задании
Задание 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 на схеме.
В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.»
Тут у нас и граф симметричный и несколько двойных, тройных вершин. Нужно анализировать не только их соседние вершины, но и соседей этих соседних вершин. Это может занять много времени. В конце концов гораздо проще иметь под рукой шаблонное решение, которое всегда даст верный ответ, правда?
Давайте как раз и выведем такой код. Давайте подумаем, а что мы делали при ручном решении?
Мы искали какую-то «особенную» точку. И говорили, буквально следующее: «а что, если пункту А соответствует номер 1?». Да, вручную мы сразу искали зависимости и сразу определяли подходящие номера для пунктов.
Но как бы нам следовало поступить, будь у нас куда больше времени, но меньше «интуиции», которая бы нам подсказывала? Скорее всего мы бы просто «выстреливали» предположениями: «Пусть А=1, B=2, C=3 и т.д.» и проверяли, сходится ли матрица с графом. Если нет, то переставляли бы номера и проверяли снова и так, пока не наткнёмся на верное соотношение номеров и букв.
Так давайте заставим компьютер переставлять все возможные значения пунктов пока не будет найдено подходящее! Начнём писать наш код.
Здесь не просто так несколько раз прозвучало слово «перестановки». Именно их мы будем использовать в коде. А реализует перестановки функция permutations из модуля itertools — импортируем её:
Далее нам нужно переписать все рёбра графа. То есть буквально выбираем любую точку и от неё идём по часовой, против часовой, по диагонали — не важно. Главное выписать все рёбра! Здесь 9 рёбер (дорог) и запишем их в виде строки, которую разделим на части по пробельному символу. Таким образом получим список строк graph:
В graph содержится такой список:
Теперь запишем таблицу из условия. Как это сделать: смотрим на каждую строку по очереди. Выписываем номера тех столбцов, под которыми стоит «звёздочка» в этой строке. Например, в строке 1 «звёздочки» стоят под столбцами 2, 3 и 4. Это означает, что из пункта 1 есть дороги в пункты 2, 3 и 4.
Записывать из будем аналогично с рёбрами: в одну строку, которую разделим через split():
В переменной matrix у нас такой список:
То есть первый элемент этого списка — matrix[0] — это строка 234, второй — 136. Иными словами, каждый элемент списка означает, в какие пункты из него есть дороги.
Можем приступать к перебору всех возможных перестановок вершин. Делать это, конечно же, будет в цикле for:
Именно permutations() создаёт перестановки всех вершин нашего графа, например, так:
Это означает, что вершине F соответствует номер 1 из матрицы смежности, D — 2 и так далее.
То есть позиция буквы в кортеже равна номеру пункта матрицы. Но тут есть одна загвоздка. Мы то с вами считаем от единицы. А вот нумерация индексов в программировании идёт с нуля. То есть у буквы F индекс 0, но номер 1. Значит, чтобы получить номер буквы (вершины) нужно к её индексу добавить единицу. Это нам пригодится далее.
Теперь нужно написать самую страшную и сложную строку, которая как раз и будет проверять соответствие рёбер и вершин. Выглядит она так:
Разберём её по частям. Начнём с цикла «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». Где x — это условный «столбец» матрицы, а y — строка. То есть мы ищем цифру столбца среди цифр, которые мы переписывали построчно с матрицы.
Давайте прямо подставим известные нам значения. Иными словами проверяется, есть ли число 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):
В итоге весь код у нас выглядит так:
Запускаем его и получаем такие два кортежа:
Такое может произойти только в двух ситуациях:
- Граф симметричный
- Вы ошиблись в записи рёбер или номеров вершин
К счастью, у нас первый вариант — граф действительно симметричный и об этом мы сказали еще в самом начале.
В задании же от нас требовалось найти номера пунктов B и C. Просто посчитаем порядковый номер каждой буквы в кортеже (только в одном из двух кортежей!). Значению B соответствует номер 3, а C — 7. Значит в ответ запишем число 37.
Пример
Решим еще одно задание программным методом. Формулировка будет такой:
«На рисунке изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера в таблице могут соответствовать населённым пунктам D и Е на схеме.
В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.»
Импортируем нужную функцию, перепишем все рёбра и номера вершин из матрицы:
Запустим цикл и проверку условия:
И теперь давайте не вручную искать нужные номера для пунктов D и Е, а сразу из текущей перестановки (i) получим номера этих вершин через метод index() и отсортируем эти номера в порядке возрастания функцией sorted().
Таким образом на экране мы сразу увидим нужные для ответа значения.
Вся программа будет выглядеть так:
А выводить она будет числа 5 и 7, которые и запишем в ответ.
На этом мы закончим разбор первого типа 1 задания ЕГЭ по информатике. А в следующей статье уже познакомимся со вторым типом, научимся работать с весовой матрицей и также решим задания двумя методами: ручным и программным.
<<< Предыдущая статья Следующая статья >>>