Условие.
Такой тип был на ЕГЭ в июне и на ЕГКР 27.04.24
На рисунке справа схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам G и D на схеме.
В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания. Условия взяли с https://kompege.ru/task, но решения там нет, давайте РЕШИМ сами!
Решение
1 строка программы. Будем использовать встроенный модуль itertools, который нужен нам для генерации всех перестановок списка.
А в этом модуле - функцию permutations().
В строке 2 (где graph) прописываем каждую вершину, а после двоеточия перечисляем все вершины, в которые из неё можем попасть напрямую. Смотрим это на рисунке, на графе. Тут важно сконцентрироваться.
Строка 3 и matrix. Тут всё просто, каждая строка таблицы превращается в строку здесь, если есть пересечение пишем w, если нет, то пишем точку.
Дальше для удобства нахождения ответа печатаем себе номера столбцов, повторюсь, это исключительно для удобства.
Начиная со строки 12 у нас цикл, который, если прям простыми словами, подбирает такие перестановки, при которых образуется полное соответствие таблицы и графа.
import itertools
graph={'a':'bcg','b':'aeg', 'c':'adf','d':'fc', 'e':'bf', 'f':'ecd', 'g':'ba'}
matrix = (
'.w.w.w.'+
'w....w.'+
'....w.w'+
'w...w..'+
'..ww..w'+
'ww....w'+
'..w.ww.')
print (' 1 2 3 4 5 6 7') # № столбцов, 4 пробела поставил между цифрами
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)
В ответе от нас хотят номера столбцов, которые соответствуют G и D, в порядке возрастания, значит пугаться того, что напечатано 2 расклада не нужно, это обычная ситуация для этого задания, даже если спросят расстояние, ведь дорога из D в G равна дороге из G в D, что логично.
Таким образом ответ: 23.
ПОДПИСЫВАЕМСЯ, СТАВИМ ЛАЙКИ, ПИШЕМ КОММЕНТАРИИ, ВОПРОСЫ, СЛЕДИМ ЗА ОБНОВЛЕНИЯМИ :) СПАСИБО ЗА ВНИМАНИЕ! #информатикаегэ #егэпоинформатике2024 #июнь #резерв