2014 dxdy logo

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

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




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

 
 
 
 Re: Рекурсия в C++
Сообщение13.08.2020, 21:16 
Создайте два контейнера: 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 
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 
Аватара пользователя
А почему рекурсия? Просто обход расширяющегося списка.

 
 
 
 Re: Рекурсия в C++
Сообщение15.08.2020, 17:07 
Спасибо. Это спрашивалось в связи с этой темой
topic142136.html
но там такой забил фонтан идей, что всё изменилось.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group