В прошлой статье мы уже познакомились с алгоритмом решения первого типа задания 1 ЕГЭ по информатике. Научились работать с матрицей смежности и разобрали как ручной, так и программный методы решения.
В этой статье мы посвятим себя разбору второго типа заданий и узнаем, как находить длины нужных рёбер по весовой матрице. По большому счёту, значительная часть решения повторяется: и в первом, и во втором типе нужно сопоставить номера матрицы с буквами на графе. Только после этого здесь предстоит найти веса заданных рёбер и сложить их.
Сложностей в этом возникнуть не должно, так что давайте приступать к решению заданий. Как и в прошлой статье, сначала решим одно задание исключительно вручную, а затем закрепим программный метод решения на двух примерах.
Начнём мы с такой формулировки:
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт G и из пункта A в пункт C.
Начинаем ручное решение с расстановки степеней вершин. Чтобы понять, какая степень у нужной нам вершины, достаточно просто подсчитать количество рёбер, соединённых с ней. Так, например, из вершины G выходят три отрезка, следовательно, и её степень равна трём.
Здесь мы имеем три вершины со степенью 2 — E, A и B. И четыре вершины со степенью 3 — F, C, D и G. Степени вершин отмечены на графе оранжевыми цифрами.
Важно: в весовой матрице степень вершины определяем по количеству заполненных ячеек в строке, а не по сумме записанных в них чисел. Сами числа показывают длины дорог.
Теперь нужно найти какую-нибудь необычную вершину. Здесь E — единственная вершина степени 2, которая соединена с двумя вершинами степени 3. Давайте попробуем найти её в матрице. Для этого перебираем строки и сначала ищем те, в которых записано 2 числа.
Если это условие выполняется, то мы смотрим на оба столбца, в которых эти числа записаны. Нужно, чтобы в этих столбцах было по три числа (тройные вершины).
Например, в строке 2 у нас два числа: 21 в столбце 4 и 13 в столбце 6. Первое условие выполнено.
Теперь проверяем четвёртый столбец: в нём всего 2 числа — 30 и 21, а должно быть три! Значит, строка 2 нам не подходит.
Идём дальше, строка 4 вроде бы может подойти, в ней тоже есть два числа: 30 и 21. И в столбце 1 всё тоже пока хорошо, три числа (30, 3 и 5), как и должно быть. Но всё портит столбец 2 — ведь в нём 2 числа, следовательно, вершина соединяется всего с двумя другими, а не тремя, как требуется.
И, наконец, осталась строка под номером 7. Очевидно, что она нам подходит — соединяется с двумя тройными вершинами под номерами 1 и 3. Отсюда делаем вывод, что вершина E имеет номер 7.
Также можем предположить, что вершины F и С имеют номера 1 или 3, поскольку с ними соединяется вершина E (7). Давайте определим, какой именно номер имеет каждая из них. Обратите внимание, что вершина F соединяется с двумя тройными и одной двойной вершиной. А C — наоборот, с двумя двойными и одной тройной. Что это значит?
Это значит, что в строке, которая соответствует вершине C, должно быть 3 числа, в двух столбцах с этими числами должно быть по 2 числа, а в одном — 3 числа.
Рассмотрим строку с номером 1. Она соединяется со столбцами под номерами 4, 5 и 7 (Е).
Теперь смотрим на столбцы 4, 5 и 7. В столбцах 4 и 7 по два числа, в столбце 5 — три.
Условие выполняется, вершина под номером 1 соединена с двумя двойными и одной тройной. Можем смело говорить, что вершина С имеет номер 1. Тогда номер 3 достаётся вершине F.
Можем теперь найти вершину G: она соединяется с только что найденными C и F и ещё одной тройной вершиной D. Нам нужно просто найти такую строку, которая будет иметь числа в столбцах C (1) и F (3), а также ещё в одном. Такой строкой является пятая. Значит, вершина G имеет номер 5.
Не забываем и про ещё одну вершину, с которой соединена G, — вершину D. В той же пятой строке видим число 8, расположенное в 6 столбце. Следовательно, вершине D присвоим номер 6.
Оставшиеся вершины определить несложно. Вершина A должна соединяться с вершиной С под номером 1, а вершина B — с D, которая имеет номер 6.
С первым номером у нас соединяется только 4, следовательно, вершина А будет иметь номер 4. А оставшаяся вершина B — 2.
Готово, мы соотнесли вершины графа с номерами из весовой матрицы. Осталось лишь найти вес рёбер AC и DG. Ищем числа на пересечении столбца A и первой строки (C) и на пересечении столбца D с пятой строкой (G).
Такими числами являются 30 и 8. Складываем их и получаем ответ на это задание — число 38.
Теперь вспомним программный метод решения задания 1. На очереди у нас такая формулировка:
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта A в пункт G и из пункта D в пункт E.
Итак, подробно разбирать весь код мы не будем. Этому мы уделили немало внимания ещё в прошлой статье. Просто вкратце напомним, что делает наш код.
Сначала нам нужно описать структуру нашего графа:
graph, просто переписывая их с графа (BD, DG, GA и так далее)В коде это будет выглядеть так:
from itertools import permutations
graph = 'BD DG GA AF FH HC CB BE ED EH GF'.split()
matrix = '234 157 147 138 268 58 23 456'.split()Далее следует перебор всех возможных вариантов перестановок букв A-H. То есть мы пытаемся подобрать их правильное расположение: это может быть ABCDFEHG, GHEFABCD или какое-либо другое. Для этого используем функцию permutations() из модуля itertools. Каждую из таких перестановок перебираем в цикле for:
from itertools import permutations
graph = 'BD DG GA AF FH HC CB BE ED EH GF'.split()
matrix = '234 157 147 138 268 58 23 456'.split()
for i in permutations('ABCDEFGH'):И самая главная строка:
if all(str(i.index(x) + 1) in matrix[i.index(y)] for x, y in graph):Это сердце кода. Мы берём каждую перестановку и проверяем её на «истинность». Логика такая:
graph (пару соседних вершин x и y)i.index(x) + 1 и i.index(y) + 1all() следит за тем, чтобы это условие выполнялось для всех рёбер сразу. Если хотя бы одна дорога из списка graph не «прописана» в matrix для этой комбинации букв, этот вариант нам не подходит.В конце останется лишь вывести на экран текущую расстановку:
print(*i)Весь код у нас выглядит так:
from itertools import permutations
graph = 'BD DG GA AF FH HC CB BE ED EH GF'.split()
matrix = '234 157 147 138 268 58 23 456'.split()
for i in permutations('ABCDEFGH'):
if all(str(i.index(x) + 1) in matrix[i.index(y)] for x, y in graph):
print(*i)На выходе получаем: E H B D F A C G. Читаем результат слева направо: E — 1, H — 2, B — 3 и так далее. Отметим соответствия на матрице и найдём числа на пересечении EH и GA.
Этими числами являются 7 и 4, складываем их и пишем в ответ число 11.
Для закрепления решим ещё одно задание программным способом. Формулировка будет такой:
На рисунке изображена схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта A в пункт D и из пункта B в пункт E.
Выписываем рёбра графа и значения из весовой матрицы:
from itertools import permutations
graph = 'AB BE EH HC CA DA DB DG DF FC GE GH'.split()
matrix = '2347 16 158 157 348 278 146 356'.split()И далее абсолютно ничего не изменяем в нашем шаблонном коде:
from itertools import permutations
graph = 'AB BE EH HC CA DA DB DG DF FC GE GH'.split()
matrix = '2347 16 158 157 348 278 146 356'.split()
for i in permutations('ABCDEFGH'):
if all(str(i.index(x) + 1) in matrix[i.index(y)] for x, y in graph):
print(*i)Выдаёт наш код следующее расположение букв: D F G B E C A H. Отмечаем их на матрице и ищем числа на пересечении AD и BE.
В ответ запишем сумму найденных чисел — 14.
Во втором типе задания 1 сначала сопоставляем буквы на графе с номерами в матрице и только потом ищем длины нужных дорог. Не складывайте числа, пока соответствие вершин не найдено полностью.
На этом разбор задания 1 закончен. Теперь у нас есть два способа решения — ручной и программный. Выбирайте тот, который удобнее, но обязательно проверяйте, все ли рёбра графа перенесены без ошибок.
А попрактиковаться в решении заданий данного типа вы можете в нашем тренажёре.
