2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Рекурсия в C++
Сообщение13.08.2020, 17:32 
Заслуженный участник


31/12/15
922
Дан список людей (на самом деле некоторых объектов, в списке указатели на них). Для каждого человека есть список его детей (тоже список указателей). Списки детей могут перекрываться (у разных людей бывают общие дети). Программа должна по данному человеку выдавать список всех его потомков (его самого, детей, внуков, правнуков и т.д.) без повторений. В функциональном языке я бы сделал так: функция кладёт в список самого человека, а потом рекурсивно применяется ко всем его детям. Получается список с повторами, повторы потом удаляем. Можно сразу удалять повторы, определив функцию с двумя параметрами (человек и список людей), она перечисляет потомков этого человека, не входящих в этот список, определение рекурсивное. Как это правильно сделать на C++?

 Профиль  
                  
 
 Re: Рекурсия в C++
Сообщение13.08.2020, 21:16 
Заслуженный участник


26/05/14
981
Создайте два контейнера: grey, black. Контейнеры хранят людей без повторений.
Код:
Container grey(start_list_of_people);
Container black;
while (!grey.empty()) {
    Man man = grey.remove_some();
    if (!black.contains(man)) {
        black.put(man);
        grey.put(man.children());
    }
}
return black;

 Профиль  
                  
 
 Re: Рекурсия в C++
Сообщение13.08.2020, 23:06 


09/05/16
138
george66 в сообщении #1478880 писал(а):
Программа должна по данному человеку выдавать список всех его потомков (его самого, детей, внуков, правнуков и т.д.) без повторений.


Если используете C++ $\ge 11$ и можете задать size_t std::hash<Person>::operator() (например, можете гарантировать, что два Person* отличаются тогда и только тогда, когда отличаются указатели, или можете гарантировать уникальность имени, от которого можно взять std::hash<std::string>()), то детей можно сложить в стандартный std::unordered_set<Person>.

Хотя стоп. Если каждый человек уникально определяется указателем Person*, то достаточно собрать множество указателей std::unordered_set<Person*>, поскольку для любых указателей std::hash уже определён.

 Профиль  
                  
 
 Re: Рекурсия в C++
Сообщение15.08.2020, 13:46 
Заслуженный участник
Аватара пользователя


15/10/08
11533
А почему рекурсия? Просто обход расширяющегося списка.

 Профиль  
                  
 
 Re: Рекурсия в C++
Сообщение15.08.2020, 17:07 
Заслуженный участник


31/12/15
922
Спасибо. Это спрашивалось в связи с этой темой
topic142136.html
но там такой забил фонтан идей, что всё изменилось.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group