Форум программистов, компьютерный форум, киберфорум
Наши страницы

Алгоритм для деревьев - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Сортировка структуры в бинарном файле http://www.cyberforum.ru/cpp-beginners/thread546415.html
приветствую всех! появилась небольшая заминка у меня - немогу сравнить значения структуры, для того, чтоб отсортировать ее в бинарном файле. суть задачи: 1.Создать файл F1.dat, содержащий 8...
C++ Переписать реализацию стека с использованием ООП Найти элемент с заданным ключом в стеке . У меня написана программа эта через структуру . Нужно переписать её через классы при этом использовать private , public, конструктор по умолчанию,... http://www.cyberforum.ru/cpp-beginners/thread546391.html
C++ Вывести на экран числа в виде таблицы [Borland C++]
Задача: Выведите на экран числа в виде следующей таблицы: 6 6 6 6 6 7 7 7 7 8 8 8 9 9 10
C++ Вычислить площадь пересечения двух окружностей
Здравствуйте) Может кто-нибудь сталкивался с написнием программы для вычисления площади пересечения двух кругов? помогите, пожалуйста...
C++ Вычисление n-го члена ряда Фибоначчи и n-го члена арифметической прогрессии http://www.cyberforum.ru/cpp-beginners/thread546379.html
Пожалуйста помогите составить блок схему , код программы и файл exe используя цикл while составить программу которая вычисляет n-й член ряда Фибоначчи и n-й член арифметической прогресии пока они не...
C++ Разработать нерекурсивную функцию, которая для заданного натурального числа N возвращает сумму его делителей Разработать функцию, которая для заданного натурального числа N возвращает сумму его делителей. с помощью данной функции:вывести на экран только целые числа отрезка , у которых сумма делителей равна... подробнее

Показать сообщение отдельно
html-profi
5 / 5 / 0
Регистрация: 25.11.2011
Сообщений: 54

Алгоритм для деревьев - C++

12.04.2012, 21:45. Просмотров 918. Ответов 0
Метки (Все метки)

Всем привет!
Препод дал задание написать программу, которая бы находила максимальное независимое множество в дереве(т.е. дано дерево, надо найти максимальное множество вершин, никакие две из которых не связаны ребром)
Нашел на псевдокод
function get_independent_set(Node u)
{
если I(u) уже посчитано, то возвратить I(u)
//мощность множества, которое можно получить, если не брать вершину u
children_sum = 0
//мощность множества, которое можно получить, если взять вершину u
grandchildren_sum = 0
//цикл по всем детям
for i := 1 to child_num do
children_sum = children_sum + get_independent_set(children[i])
//цикл по всем внукам
for i:= 1 to grandchildren_num
grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i])
//запоминаем, чтобы не персчитывать ещё раз
I(u) = max(1 + grandchildren_sum, children_sum)
возвратить I(u)
}

но ничего не пойму. Помогите плиз.
Буду благодарен за помощь.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru