В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель. Каждому элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя. Вам нужно написать программу, которая по заданному генеалогическому древу определяет высоту всех его элементов
Программа получает на вход количество человек в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента дерева, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.
Программа должна вывести список всех элементов древа в лексикографическом порядке (по алфавиту). После вывода имени каждого элемента необходимо вывести его высоту.
Пример 1:
Введите количество человек: 9
1 пара: Alexei Peter_I
2 пара: Anna Peter_I
3 пара: Elizabeth Peter_I
4 пара: Peter_II Alexei
5 пара: Peter_III Anna
6 пара: Paul_I Peter_III
7 пара: Alexander_I Paul_I
8 пара: Nicholaus_I Paul_I
“Высота” каждого члена семьи:
Alexander_I 4
Alexei 1
Anna 1
Elizabeth 1
Nicholaus_I 4
Paul_I 3
Peter_I 0
Peter_II 2
Peter_III 2
Решение:
number_people = int(input('Введите количество человек: '))
data_dict = dict()
level_dict = dict()
# Должно быть number_people + 1, но в примере на 1 меньше. Не стал прибавлять.
# TODO так и есть в задании: "Далее следует N−1 строка"
for i in range(1, number_people):
descendant_name, parent_name = input(f'{i} пара: ').split()
data_dict[descendant_name] = parent_name
level_dict[descendant_name] = 0
level_dict[parent_name] = 0
for i in data_dict:
people = i
while people in data_dict:
people = data_dict[people]
level_dict[i] += 1
print('\n“Высота” каждого члена семьи:')
for i in sorted(level_dict):
print(i, level_dict[i])
Как можно отблагодарить:
- Оформить удобную для вас подписку на Boosty.to
- Разово поддержать через DonationAlerts
