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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
html-profi
5 / 5 / 0
Регистрация: 25.11.2011
Сообщений: 54
#1

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

12.04.2012, 21:45. Просмотров 907. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2012, 21:45
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм для деревьев (C++):

Массив: Учащиеся участвовали в посадке деревьев. Сколько деревьев было посажено - C++
1)Учащиеся 8-х классов участвовали в посадке деревьев. 8-а посадил 100 деревьев, 8-б —122 дерева, 8-в — 98 деревьев, 8-г — 104 дерева, 8-д...

Создать функции ввода/вывод для бинарных деревьев - C++
Не могу создать функции ввода/вывод для бинаных деревьев. очень срочно нужно! скажите где ошибка... Вот текст: #include ...

Помогите алгоритм для char переделать в алгоритм для float - C++
char* DecToBin(char x, char* str) { int i; for (i = sizeof(x)*8-1; i>=0; i--) { str = (x&1 == 1) ? '1' : '0'; x = x >>...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

Слияние деревьев - C++
Сижу, мучаюсь, не могу понять что подразумевается в задании о слиянии деревьев. Подвесить вершину второго дерева к какому-нить листу 1-го?...

Реализация деревьев - C++
Я вот сделал простое дерево (максимально дочерних узлов в корне - 3). Теперь нужно доработать, чтобы были списки сыновей. Помогите...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2012, 21:45
Привет! Вот еще темы с ответами:

Турнирная сортировка деревьев - C++
Здравствуйте, программа турнирная сортировка деревьев. Но проблема в том, что при компиляции выдает ошибку. Помогите, пожалуйста ...

Слияние бинарных деревьев - C++
Слияние - это функция выбора элемента из двух Берем два дерева; функцию, которая выбирает один элемент из двух T fun(T x1, Tx2); ...

Итеративная функция сравнения деревьев - C++
Задание такое: Рекурсивно и итеративно описать логическую функцию, проверяющую на равенство деревья Т1 и Т2. Рекурсивная функция есть,...

Сравнить структуру двух деревьев - C++
Написать два варианта функции(с рекурсией и без). Даны два дерева,два указателя на корни. Функция возвращает логическое значение:если...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru