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