Задание 1. Информатика. ЕГЭ. Статград. 24.10.2024-1
- Просмотры: 325
- Изменено: 24 ноября 2024
На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населёнными пунктами.
|
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно без пробелов и знаков препинания указанные на графе буквенные обозначения пунктов от П1 до П9: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.
Решение:
Python
from itertools import permutations
graph = {'А': set('БГД'),
'Б': set('АВД'),
'В': set('БЕ'),
'Г': set('АЖ'),
'Д': set('АБЖИ'),
'Е': set('ВИК'),
'Ж': set('ГДИ'),
'И': set('ЕДЖК'),
'К': set('ИЕ')}
templ = {1: [2, 4, 9],
2: [1, 7],
3: [4, 5, 6],
4: [1, 3, 6, 9],
5: [3, 8],
6: [3, 4, 7, 8],
7: [2, 6, 8],
8: [5, 6, 7],
9: [1, 4]}
for p in permutations('АБВГДЕЖИК'):
check = {p[k-1]: set([p[i-1] for i in v]) for k, v in templ.items()}
if check == graph:
print(''.join(p))
Ответ: ЕВЖИГДБАК
Видео с разбором