Задание 1. Информатика. ЕГЭ. Шастин. 13.03.2025
- Просмотры: 144
- Изменено: 14 марта 2025
(Д. Бахтиев) На рисунке схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Д и Е на схеме. В ответе запишите эти номера в порядке возрастания, без пробелов и знаков препинания.
Решение:
Python
from itertools import permutations
graph = {'А': set('БЖЗ'),
'Б': set('АВГ'),
'В': set('БГ'),
'Г': set('БВД'),
'Д': set('ГЕ'),
'Е': set('ДЖ'),
'Ж': set('АЕЗ'),
'З': set('АЖ')}
templ = {1: [3, 5, 7],
2: [4, 6, 8],
3: [1, 5],
4: [2, 7],
5: [1, 3, 6],
6: [2, 5, 8],
7: [1, 4],
8: [2, 6]}
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 8')
print(*p)
Вывод программы
1 2 3 4 5 6 7 8 Г Ж В Е Б А Д З 1 2 3 4 5 6 7 8 Ж Г З Д А Б Е В
Ответ: \(47\)