Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
144 / 144 / 32
Регистрация: 26.10.2008
Сообщений: 782
1

В БПД найти путь максимальной длины между вершинами разной высоты с минимальной суммой конечных вершин.

19.02.2010, 23:17. Просмотров 1499. Ответов 3
Метки нет (Все метки)

Есть такая задача:
Найти путь максимальной длины между вершинами разной высоты с минимальной суммой конечных вершин. Если таких путей несколько, то выбрать из них тот, у которого корневая вершина имеет наименьшее ключевое значение. Удалить (правым удалением), если существует, среднюю по значению вершину этого пути.
Замечание.
В случае неоднозначности выбора удаляемой вершины (например, несколько путей максимальной длины между вершинами разной высоты и с минимальной суммой ключей конечных вершин имеют один и тот же корень, но средние по значению вершины этих путей не совпадают) ничего из дерева удалять не нужно.
Пример входных данных
10, 5, 12, 11
Пример выходных данных, полученных прямым левым обходом итогового дерева
11, 5, 12

Не могу понять, как получились выходные данные.
Исходя из входных данных, дерево имеет следующий вид:


Возможные пути имеют вид:
5-10, 10-12, 10-12-11, 5-10-12-11

Самый длинный путь имеет здесь: 5-10-12-11.
Средней вершины в нём вообще не существует, т.к. длина пути чётная.
Но в выходных данных удалена вершина 10, которая вообще не является средней ни в каком из путей.

Скажите, пожалуйста, в чём я ошибаюсь?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.02.2010, 23:17
Ответы с готовыми решениями:

Найти путь максимальной длины между вершинами разной высоты бинарного дерева
Я уже задавал аналогичный вопрос в другом разделе форума, но там просмотров меньше чем в этом...

Деревья, выбрать путь максимальной длины, у которого сумма ключей конечных вершин минимальна
среди всех путей дерева, соединяющих вершины на разной высоте, выбрать путь максимальной длины, у...

Найти путь максимальной длины, и проходящий через заданное множество вершин
5)Дано бинарное дерево. Найти путь максимальной длины, и проходящий через заданное множество...

Найти в дереве путь максимальной длины, и проходящий через заданное множество вершин
Дано бинарное дерево. Найти путь максимальной длины, и проходящий через заданное множество вершин.

3
Эксперт С++
7174 / 3233 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
20.02.2010, 18:52 2
Полный текст задания есть ?

Добавлено через 22 секунды
А то тут чувствуется что чего-то не хватает ...
0
144 / 144 / 32
Регистрация: 26.10.2008
Сообщений: 782
21.02.2010, 01:20  [ТС] 3
Есть ещё один пример входных и выходных данных:
Пример входных данных:
10, 8, 6, 7, 20, 30, 31
Пример выходных данных:
10, 8, 6, 7, 20, 30, 31
Но в этом случае ничего не удаляется.
0
1 / 1 / 0
Регистрация: 12.02.2011
Сообщений: 5
12.02.2011, 17:03 4
.::.DIMA.::. или кто нибудь из знающих, не мог бы помочь придумать алгоритм для нахождения пути указанного в условии?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.02.2011, 17:03

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Найти на графе путь между двумя вершинами, который содержит ребра как можно большей длины
Может кто-нибудь написать последовательность действий или, если у такого алгоритма есть название,...

В файле определить разность между максимальной и минимальной суммой кредита
Помогите с заданием В файле определить разность между максимальной и минимальной суммой кредита...

Даны координаты вершин треугольника АВС. Найти длины медианы, высоты, биссектрисы, проведенные из вершин А
Даны координаты вершин треугольника АВС. Найти длины медианы, высоты, биссектрисы, проведенные из...

Выбрать 4 числа с минимальной разницей между максимальным и минимальным числом из 4 векторов разной длины
Здравствуйте, у меня такая задача: Даны 4 вектора размера от 1 до 100 000 В каждый записываются...


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

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

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