Антон стажируется в группе обработки комментариев и отзывов. Для проверки гипотезы об…
- User
Антон стажируется в группе обработки комментариев и отзывов. Для проверки гипотезы об автоматической генерации текстов Антон должен построить граф подстрок существующих текстов.
Антон берёт все имеющиеся у него слова и действует следующим образом:
слово �
� 1 � 2 . . . � � − 1 � � S=s 1 s 2 ...s n−1 s n образует � − 2 n−2 слова длины 3: � 1
� 1 � 2 � 3 w 1 =s 1 s 2 s 3 , � 2
� 2 � 3 � 4 w 2 =s 2 s 3 s 4 , � 3
� 3 � 4 � 5 w 3 =s 3 s 4 s 5
… … � � − 2
� � − 2 � � − 1 � � w n−2 =s n−2 s n−1 s n ; если для какого-то из слов � � w i еще нет вершины в графе, то она создается; для каждой пары слов ( � � , � � + 1 ) (w i ,w i+1 ) добавляется ориентированное ребро веса 1, или увеличивается вес существующего ребра на 1. Таким образом получается граф � G с � v вершинами и � e ориентированными рёбрами. Между некоторыми вершинами может быть несколько дуг (от � a к � b и от � b к � a).
По заданному набору слов помогите Антону найти количество вершин в графе и вывести ориентированные рёбра между вершинами.
- Assistant
Решение:
Для начала нужно построить граф. Для этого нужно пройтись по всем возможным подстрокам длины 3 и создать для них вершины в графе. Для каждой пары подстрок, которые следуют друг за другом в словах, нужно добавить ребро в графе между соответствующими вершинами. Если вершины соответствующей подстроки еще нет в графе, то ее нужно создать.
Пример кода на Python:
words = ["abc", "bcd", "cde"] graph = {} # словарь, где каждому слову соответствует множество вершин, инцидентных ему ребрами
for word in words: for i in range(len(word) - 2): s = word[i:i+3] # текущая подстрока длины 3 if s not in graph: graph[s] = set() # создаем вершину в графе для текущей подстроки for i in range(len(word) - 3): s1 = word[i:i+3] # первая подстрока длины 3 s2 = word[i+1:i+4] # вторая подстрока длины 3, следующая за первой graph[s1].add(s2) # добавляем ребро от первой подстроки к второй
выводим количество вершин в графе и ребра между каждой парой вершин
print(len(graph)) for vertex1 in graph: for vertex2 in graph[vertex1]: print(vertex1 + "->" + vertex2)
- User
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель. Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя. Вам дано генеалогическое древо, определите высоту всех его элементов.
Формат ввода Программа получает на вход число элементов в генеалогическом древе � N. Далее следует � − 1 N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имяпотомка имяродителя.
Формат вывода Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.
Примечание Эта задача имеет решение сложности � ( � ) O(n), но вам достаточно написать решение сложности � ( � 2 ) O(n 2 ) (не считая сложности обращения к элементам словаря). Пример ниже соответствует приведенному древу рода Романовых.
- Assistant
Решение:
Можно представить генеалогическое древо в виде словаря, где ключами будут имена людей, а значениями - их высота в дереве. Для родоначальника высота будет равна 0, а для всех остальных людей она будет на 1 больше, чем у их родителя. Для этого нужно считывать пары потомок-родитель и обновлять значения высот в словаре.
После того, как высоты всех людей известны, нужно вывести список всех элементов дерева в лексикографическом порядке и их высоты.
Пример кода на Python:
n = int(input()) # количество людей в дереве
tree = {"global": 0} # словарь, в котором хранятся высоты людей в дереве
начинаем с родоначальника
for i in range(n - 1): child, parent = input().split() tree[child] = tree[parent] + 1 # высота потомка на 1 больше высоты родителя
выводим имена людей в лексикографическом порядке и их высоты
for person in sorted(tree.keys()): print(person, tree[person])
- User
но нам же нужно у всех потомков на 1 увеличить значение высоты!
- Assistant
Действительно, в условии написано, что высота на 1 больше, чем у родителя, а не +1 для родоначальника и на 1 увеличить у каждого потомка. Спасибо за замечание.
Исправленный код на Python:
n = int(input()) # количество людей в дереве
tree = {"global": 0} # словарь, в котором хранятся высоты людей в дереве
начинаем с родоначальника
for i in range(n - 1): child, parent = input().split() tree[child] = tree[parent] + 1 # высота потомка на 1 больше высоты родителя
увеличиваем высоту у всех людей в дереве на 1
for person in tree: tree[person] += 1
выводим имена людей в лексикографическом порядке и их высоты
for person in sorted(tree.keys()): print(person, tree[person])