Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

Антон стажируется в группе обработки комментариев и отзывов. Для проверки гипотезы об…

  1. 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).

    По заданному набору слов помогите Антону найти количество вершин в графе и вывести ориентированные рёбра между вершинами.

  2. 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)

  3. User

    В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель. Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя. Вам дано генеалогическое древо, определите высоту всех его элементов.

    Формат ввода Программа получает на вход число элементов в генеалогическом древе � N. Далее следует � − 1 N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имяпотомка имяродителя.

    Формат вывода Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.

    Примечание Эта задача имеет решение сложности � ( � ) O(n), но вам достаточно написать решение сложности � ( � 2 ) O(n 2 ) (не считая сложности обращения к элементам словаря). Пример ниже соответствует приведенному древу рода Романовых.

  4. 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])

  5. User

    но нам же нужно у всех потомков на 1 увеличить значение высоты!

  6. 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])