Задание 1. Информатика. ЕГЭ. Шастин. 9.2.2025
- Просмотры: 695
- Изменено: 10 февраля 2025
(Л. Шастин) На рисунке схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам В и Е на схеме. В ответе запишите эти номера в порядке невозрастания, без пробелов и знаков препинания.
Решение:
Python
from itertools import permutations
graph = {'А': set('БВГ'),
'Б': set('АВ'),
'В': set('АБЕ'),
'Г': set('АД'),
'Д': set('ГЕЖ'),
'Е': set('ВДЖ'),
'Ж': set('ДЕ'),}
templ = {1: [2, 5], 2: [1, 3, 7], 3: [2, 6, 7], 4: [5, 6], 5: [1, 4, 6], 6: [3, 4, 5], 7: [2, 3]}
for p in permutations('АБВГДЕЖ'):
chk = {p[k-1]: set([p[i - 1] for i in templ[k]]) for k in templ}
if graph == chk:
print('1 2 3 4 5 6 7')
print(*p)
Вывод программы
1 2 3 4 5 6 7 Г А В Ж Д Е Б 1 2 3 4 5 6 7 Г Д Е Б А В Ж
Ответ: \(63\)