Задача 1 ЕГЭ по информатике - решаем на Питоне

Хотите готовиться со мной к ЕГЭ?
Пишите:  ydkras@mail.ru
Немного обо мне.

Задача 1 (сопоставление графа и матрицы расстояний) обычно не вызывает трудностей. Однако её можно решать и программно. Решение оказалось очень простым. Наиболее кропотливая часть - ввод исходных данных. Здесь нельзя делать ни одной ошибки.

Рассмотрим данную задачу на примере из демонстрационного варианта ЕГЭ по информатике 2023 г.

Условие задачи стандартное: дан граф дорог между городами A,B,C,...,G и матрица расстояний между городами 1,2,3,...,7. Требуется установить соответствие между буквенными и цифровыми обозначениями городов и определить сумму протяжённостей дорог из пункта D в пункт B и из пункта F в пункт A.

Граф представим как словарь, в котором для каждого пункта перечислим все пункты, куда из него ведут дороги:

graph={'A':'DEF','B':'DF','C':'FG','D':'ABE','E':'ADG','F':'ABC','G':'CE'}

Матрицу расстояний представим как длинную символьную строку, где наличие дороги между городами будет обозначаться большой буквой W, а отсутствие - точкой. (Можно использовать любые символы, данные символы выбраны из соображений наглядности и простоты ввода.)

matrix=(
'.WW....' +
'W..WW..' +
'W....W.' +
'.W....W' +
'.W...WW' +
'..W.W.W' +
'...WWW.' )

 

Решим задачу "методом грубой силы": сгенерируем все возможные перестановки городов в графе и для каждой перестановки построим матрицу связи. Если построенная матрица совпадет с приведенной в условии, то нужная перестановка найдена.

Для генерации перестановок воспользуемся функцией permutations из модуля itertools.

Вот полный текст программы:

 

import itertools

graph={'A':'DEF','B':'DF','C':'FG','D':'ABE','E':'ADG','F':'ABC','G':'CE'}
matrix=(
'.WW....' +
'W..WW..' +
'W....W.' +
'.W....W' +
'.W...WW' +
'..W.W.W' +
'...WWW.' )

for p in itertools.permutations(graph):
    m = ''
    for x in p:
        for y in p:
            m += 'W' if y in graph[x] else '.'
    if m==matrix:
        print(p)


Собственно код занимает семь строк, остальное - исходные данные.

Программа выводит кортеж

('C', 'F', 'G', 'B', 'A', 'E', 'D')

Это означает, что городу C графа соответствует город 1 в таблице, городу F - город 2 и т.д. Дорога из D в B - это дорога из 7 в 4 протяженностью 53 км, а дорога из F в A - дорога из 2 в 5 протяженностью 5 км. Таким образом, ответ - 58 (53+5).

Функция itertools.permutations(graph) генерирует все возможные перестановки ключей словаря graph - это именно то, что нам требуется.

Метод "грубой силы" требует испытать все возможные перестановки городов. Их число, как известно, n! (факториал). Оно очень быстро растет с ростом числа городов, и уже при 9 городах программа выполняется достаточно медленно. Но задачи с числом городов более 9 мне не встречались.

Если сопоставление графа и матрицы неоднозначно, программа выведет все решения.

Программу можно несколько сократить:

import itertools
graph={'A':'DEF','B':'DF','C':'FG','D':'ABE','E':'ADG','F':'ABC','G':'CE'}
matrix=(
'.WW....' +
'W..WW..' +
'W....W.' +
'.W....W' +
'.W...WW' +
'..W.W.W' +
'...WWW.' )
for p in itertools.permutations(graph):
    if matrix ==''.join([''.join([('W' if y in graph[x] else '.') for y in p]) for x in p]):
        print(p)

 

Теперь собственно код занимает всего три строки. Но, кажется, что от этого он стал менее понятным. 

(c) Ю.Д.Красильников, 2023 г.