Навигация по странице
Тип 2
В прошлой статье мы уже познакомились с алгоритмом решения первого типа 1 задания ЕГЭ по информатике. Научились работать с матрицей смежности и разобрали как ручной, так и программный методы решения.
В этой статье мы посвятим себя разбору второго типа данных заданий и узнаем, как определять длину пути между двумя пунктами на графе. По большому счёту, значительная часть решения будет повторяться, что в заданиях первого типа, что в заданиях второго. Единственное отличие в том, что после того, как мы соотнесём номера матрицы и названия пунктов на графе, нужно будет еще найти в весовой матрице длину заданных рёбер.
Сложностей в этом возникнуть не должно, так что давайте приступать к решению заданий. Как и в прошлой статье, сначала решим одно задание исключительно вручную, а затем закрепим программный метод решения на двух примерах.
Алгоритм решения
Ручной метод
Начнём мы с такой формулировки:
Задание 102
«На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт G и из пункта A в пункт C.»
Начинаем ручное решение с расстановки степеней вершин. Чтобы понять, какая степень у нужной нам вершины, достаточно просто подсчитать количество отрезков, которые из неё выходят. Так, например, из вершины G выходят три отрезка, следовательно, и её степень равняется трём.
Здесь мы имеем три вершины со степенью 2 — E, A и B. И четыре вершины со степенью 3 — F, C, D и G. Степени вершин отмечены на графе оранжевыми цифрами.
Теперь нужно найти какие-нибудь необычные вершины. Здесь вершина E — единственная, которая соединяется с двумя тройными (вершинами со степенью три). Давайте попробуем найти её на матрице. Для этого мы перебираем каждую строку и смотрим, чтобы в ней было 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 — наоборот, с двумя двойными и одной тройной. Что это значит?
Это значит, что в строке, которая соотносится с вершиной С, должно быть 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 заданий. На очереди у нас такая формулировка:
Задание 103
«На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта A в пункт G и из пункта D в пункт E.»
Итак, подробно разбирать весь код мы не будем. Этому мы уделили немало внимания еще в прошлой статье. Просто вкратце напомним, что делает наш код.
Сначала нам нужно описать структуру нашего графа:
- Создаём список всех дорог (рёбер) graph просто переписывая их с графа (BD, DG, GA и так далее)
- Создаём список связей для каждой «цифры» весовой матрицы. Например, первая строка «234» говорит нам, что пункт 1 соединен с пунктами 2, 3 и 4.
В коде это будет выглядеть так:
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:
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) + 1
- Затем берём обе вершины одного ребра и проверяем, есть ли среди соседей первой вершины номер второй вершины. Простыми словами: если в графе есть дорога между B и D, то в матрице у того номера, который мы назначили букве D, должен быть в списке сосед тот номер, который мы назначили букве B.
Допустим, мы назначили букве B номер 1, а D — 2. Тогда проверяем среди соседей второй вершины — 1, 5 и 7 наличие номера 1. Если он есть, как здесь, то B и D действительно могут быть соседями при такой расстановке. - Функция all() следит за тем, чтобы это условие выполнялось для всех ребер сразу. Если хотя бы одна дорога из списка 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.
Пример 1
Для закрепления решим еще одно задание программным способом. Формулировка будет такой:
Задание 118
«На рисунке изображена схема дорог 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()
И далее абсолютно ничего не изменяем в нашем шаблонном коде:
for i in permutations('ABCDEFGH'):
if all(str(i.index(x) + 1) in matrix[i.index(y)] for x, y in graph):
print(*i)
Весь код выглядит так:
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.