Задание 1. (А. Кабанов, 2024)
Задания 1, 13. (А. Кабанов, 2023)
Новый способ решения Задания 1, Л. Шастин
Шаблон программного решения задач
на неориентированные графы
(сопоставление таблицы и графа)
Подключаем модуль itertools для возможности использования функции permutations для перебора всех возможных комбинаций вершин графа.
from itertools import *
В виде строки прописываем из таблицы, построчно, связи вершин. Например, вершина П1 в таблице связана с вершинами П3, П5 и П7. Записываем только номера вершин, получим строку: t = '357'. Записи для каждой строки разделяем пробелом. К строке применяем метод .split(), который разделит строку по пробелам. Для всей таблицы получим следующий код:
from itertools import * t = '357 34 12467 236 17 347 1356'.split()
Также, в виде строки, прописываем связи вершин графа. Каждая связь указывается только один раз парой букв. Порядок букв в паре не важен. Порядок описания связей не важен. К строке применяем метод .split(). Для графа из примера получим:
from itertools import * t = '357 34 12467 236 17 347 1356'.split() g = 'аб бв вг гк ке ед да ав вд ве ег'.split()
Далее, с помощью функции permutations получаем все возможные перестановки буквенных обозначений вершин графа:
from itertools import *
t = '357 34 12467 236 17 347 1356'.split()
g = 'аб бв вг гк ке ед да ав вд ве ег'.split()
for p in permutations('абвгдек'):
...
Для каждой перестановки проверяем, что для всех связей вершин (пары букв из списка g), порядковый номер первой буквы из пары (увеличенный на единицу, т.к. в Python индексация производится с 0), встречается в строке, номер которой соответствует второй букве из пары. Если для всех связей условие ИСТИННО, то выводим на экран такую перестановку, это - искомое решение. Законченное программное решение:
from itertools import *
t = '357 34 12467 236 17 347 1356'.split()
g = 'аб бв вг гк ке ед да ав вд ве ег'.split()
for p in permutations('абвгдек'):
if all(str(p.index(x)+1) in t[p.index(y)] for x, y in g):
print(*range(1, 8))
print(*p)
Здесь:
- с помощью переменных x и y получаем пару букв из списка g;
- с помощью метода .index() определяем индекс буквы в текущей перестановке p;
- print(*range(1, 8)) выводит в качестве заголовков нумерацию вершин от 1 до 7, через пробел;
- print(*p) выводит через пробел буквенные обозначения вершин графа искомой перестановки, соответствующие числовой номерации.
В результате выполнения программы получим:
1 2 3 4 5 6 7 г б в а к д е
Т.е. первому столбцу таблицы соответствует вершина г из графа, второму - б и т.д.
После анализа таблицы - отвечаете на вопрос, поставленный в задаче: указываете соответствие столбцов буквенным обозначениям вершин или величину связей между заданными вершинами и тому подобное.
