Вывести список всех элементов древа в лексикографическом порядке

@ChaiNZero · Регистрация: 23.11.2021

Студворк — интернет-сервис помощи студентам

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

@eaa · 19.06.2022, 22:03

ChaiNZero, и в чем проблема?

@idealist · 20.06.2022, 06:49

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def set_and_get_h(name, d_par, d_h):
    if d_par[name] == None:
        d_h[name] = 0
    if d_h[name] == None:
        if d_h[ d_par[name] ] != None:
            d_h[name] = 1 + d_h[ d_par[name] ]
        else:
            d_h[name] = 1 + set_and_get_h( d_par[name], d_par, d_h )
    return d_h[name]
#==============================================================================
d_par  = {}
n = int( input('n = ') )
for _ in range(n):
    c, p = input('потомок, родитель: ').split()
    if not p in d_par:
        d_par[p] = None
    d_par[c] = p
d_par = dict( sorted(d_par.items()) )
d_h   = dict.fromkeys(d_par, None)
for name in d_par:
    print( name, set_and_get_h(name, d_par, d_h) )

@eaa · 20.06.2022, 11:35

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def get_h(name):
    if name not in tree:
        return 0
    return get_h(tree[name]) + 1
 
 
tree = {}
names = set()
for _ in range(int(input()) - 1):
    child, parent = input().split()
    tree[child] = parent
    names |= {child, parent}
 
for name in sorted(names):
    print(name, get_h(name))

@idealist · 20.06.2022, 21:43

eaa, однако сложность здесь у вас уже нелинейная.

@Red white socks · 20.06.2022, 21:52

idealist, а если lru_cache добавить?

@eaa · 20.06.2022, 21:54

idealist, и что теперь делать?

Добавлено через 2 минуты
Red white socks, зачем?

@Red white socks · 20.06.2022, 21:57

eaa, для линейности. Может у кого-то древо от Адама идет.

@idealist · 20.06.2022, 22:03

Сообщение от eaa

и что теперь делать?

)) Ну, мы же все время как бы за скорость заморачивались...

Сообщение от Red white socks

а если lru_cache добавить?

Ну для себя лично я пока эти фишки стараюсь не использовать, как и регулярку, чтобы в чистом питоне попрактиковаться.

@Red white socks · 20.06.2022, 22:09

idealist, functools вроде как встроенная библиотека. А код от eaa гораздо прозрачнее. Да и действительно, деревья, для которых ваш код начнет показывать хоть какую-то разницу по времени, вряд ли в природе существуют.

@idealist · 20.06.2022, 22:43

Сообщение от Red white socks

деревья, для которых ваш код начнет показывать хоть какую-то разницу по времени, вряд ли в природе существуют.

Ну, в природе олимпиадных задач муливарды муливардов таки везде понапиханы!

@ChaiNZero · 02.10.2022, 13:20 **[ТС]**

Забыл добавить, надо без функции

@eaa · 02.10.2022, 13:34

ChaiNZero, сделай без функций

@Alexarh · 02.10.2022, 13:36

Не по теме:

Ну, хорошо, что хоть спустя 3 месяца вспомнил.

@ChaiNZero · 02.10.2022, 13:45 **[ТС]**

Странно тогда что я написал это сюда, если сам мог бы написать код, не правда ли?

@Red white socks · 02.10.2022, 21:13

ChaiNZero, вам выдали решения idealist и eaa. Да, они рекурсивные. Однако любую рекурсию можно заменить итеративным решением. Например, https://habr.com/ru/post/440178/ или http://www.codenet.ru/progr/other/prbook/gl8.php
Можете также самостоятельно поискать.
Если не получится, то аккурат после Нового года можно вернуться к этому вопросу.

@ChaiNZero · 03.10.2022, 01:30 **[ТС]**

Спасибо, вы мне очень помогли, не знал, что можно так

Новые блоги и статьи Все статьи Все блоги /
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .
Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .

@ChaiNZero 1 / 1 / 0 Регистрация: 23.11.2021 Сообщений: 71

	Вывести список всех элементов древа в лексикографическом порядке 19.06.2022, 18:55. Показов 1796. Ответов 16 Метки #python, #питон (Все метки) В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель. Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя. Дано генеалогическое древо, определите высоту всех его элементов. Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя. Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	19.06.2022, 22:03
	ChaiNZero, и в чем проблема? 0

@idealist 3750 / 1944 / 613 Регистрация: 21.11.2021 Сообщений: 3,706
	20.06.2022, 21:43
	eaa, однако сложность здесь у вас уже нелинейная. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	20.06.2022, 21:52
	idealist, а если lru_cache добавить? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	20.06.2022, 21:54
	idealist, и что теперь делать? Добавлено через 2 минуты Red white socks, зачем? 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	20.06.2022, 21:57
	eaa, для линейности. Может у кого-то древо от Адама идет. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	20.06.2022, 22:09
	idealist, functools вроде как встроенная библиотека. А код от eaa гораздо прозрачнее. Да и действительно, деревья, для которых ваш код начнет показывать хоть какую-то разницу по времени, вряд ли в природе существуют. 0

@ChaiNZero 1 / 1 / 0 Регистрация: 23.11.2021 Сообщений: 71
	02.10.2022, 13:20 [ТС]
	Забыл добавить, надо без функции 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	02.10.2022, 13:34
	ChaiNZero, сделай без функций 0

@Alexarh
	02.10.2022, 13:36
	Не по теме: Ну, хорошо, что хоть спустя 3 месяца вспомнил. 0

Опции темы

@ChaiNZero 1 / 1 / 0 Регистрация: 23.11.2021 Сообщений: 71
	02.10.2022, 13:45 [ТС]
	Странно тогда что я написал это сюда, если сам мог бы написать код, не правда ли? 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	02.10.2022, 21:13
	ChaiNZero, вам выдали решения idealist и eaa. Да, они рекурсивные. Однако любую рекурсию можно заменить итеративным решением. Например, https://habr.com/ru/post/440178/ или http://www.codenet.ru/progr/other/prbook/gl8.php Можете также самостоятельно поискать. Если не получится, то аккурат после Нового года можно вернуться к этому вопросу. 1

@ChaiNZero 1 / 1 / 0 Регистрация: 23.11.2021 Сообщений: 71
	03.10.2022, 01:30 [ТС]
	Спасибо, вы мне очень помогли, не знал, что можно так 0