Задание 1. Информатика. ЕГЭ. Шастин. 18.12.2024
- Просмотры: 480
- Изменено: 1 февраля 2025
(Л. Шастин) В таблице содержатся сведения о дорогах между населёнными пунктами (звёздочка означает, что дорога между соответствующими городами есть). На рисунке справа та же схема дорог изображена в виде графа.
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите последовательность номеров пунктов, соответствующих маршруту E->F->G->H->A. В ответе укажите искомую последовательность номеров в указанном порядке без разделителей.
Решение:
Python
from itertools import permutations
graph = {'A': set('BGH'),
'B': set('AC'),
'C': set('BDF'),
'D': set('CE'),
'E': set('DFH'),
'F': set('CEG'),
'G': set('AFH'),
'H': set('AEG')}
templ = {1: [5, 6, 8],
2: [3, 6],
3: [2, 4, 7],
4: [3, 6, 8],
5: [1, 7, 8],
6: [1, 2, 4],
7: [3, 5],
8: [1, 4, 5]}
for p in permutations('ABCDEFGH'):
chk = {p[k-1]: set(p[i-1] for i in v) for k, v in templ.items()}
if chk == graph:
print('1 2 3 4 5 6 7 8')
print(*p)
Ответ: \(64815\)