26 / 26 / 9
Регистрация: 25.05.2009
Сообщений: 98
|
|
1 | |
Построение бинарного дерева из двумерного массива26.05.2009, 17:02. Показов 12286. Ответов 25
Метки нет (Все метки)
Стыдно, если честно, об этом просить, но "возник стопор" и путных идей не приходит.
Суть задачи: Есть массив n*n состоящий из целых чисел. Надо создать бинарное дерево по следующему принципу: значение индексного поля корня - всегда равно 0. В 0 ряде выбирается два минимальных элемента (за исключением 0;0), меньший из которых становится левым (одно поле структуры будет равно номеру строки, второе самому элементу), другой правым. Смотрим строку с номером, соответствующим номеру того столбца, в котором находился наш элемент (то есть, если в качестве левого мы взяли элемент массива, находившийся в столбце 3, то мы будем просматривать 3 строку). Там снова выбираем два минимальных элемента. Исключением будет элемент 3;0. Далее, надо заполнять каждую из ветвей до тех пор, пока в поиске минимумов не останется только один элемент (столбцы, номера которых мы уже прошли из поиска минимумов исключаются), который становится листом. Если говорить на примере, то из такой таблицы: - 1 9 2 8 - 2 2 7 9 - 6 5 3 4 - должно получиться следующее дерево (приведены значения индексных полей): 0 / \ 1 3 / \ / \ 2 3 2 1 | | | | 3 2 1 2 Нумерация строк и столбцов здесь естественно СИшная. Буду очень благодарен, если поможете с этим делом. Если кому-либо интересно, зачем мне это - сообщаю: для решения задачи коммивояжера "жадным" алгоритмом. Но в этой модификации алгоритма выбирается не один самый близкий город, а два наиболее близких. Добавлено через 18 часов 27 минут 53 секунды Как-то криво я задачу сформировал ((. Попробую по другому: есть n городов. Стоимость перемещения из города в город - известна, причем стоимость перемещения из a в b может отличаться от стоимости перемещения из b в a. Нужно пройти все города и вернуться в 1й. Алгоритм нахождения минимального пути следующий: ищем 2 города, путь до которых из данного города имеет минимальную стоимость. Продолжаем искать такие города до тех пор, пока не будет сформирован путь по всем городам. (например, 1-2-3-4-5-1 или 1-3-5-2-6-4-1) В конечном итоге должно получится 2(n-1) путей из которых потом надо выбрать наименьший. Я планировал сделать это через бинарное дерево, однако пока не выходит ни одного нормального алгоритма. Буду благодарен, если кто-нибудь сможет подсказать, каким образом можно решить эту задачу.
0
|
26.05.2009, 17:02 | |
Ответы с готовыми решениями:
25
Построение бинарного дерева на основе не бинарного Построение бинарного дерева Построение бинарного дерева Построение бинарного дерева из строки |
26 / 26 / 9
Регистрация: 25.05.2009
Сообщений: 98
|
|
26.05.2009, 23:30 [ТС] | 3 |
как решить задачу, я примерно представляю. Даже более, чем примерно. Принцип построения путей по заданному алгоритму из n городов "на словах" - тоже прекрасно понимаю. Но реализовать это в коде тем или иным способом у меня не получается. Через массивы? Не ясно как. Оптимальным методом решения мне кажется построение дерева. Но вот с этим самым построением у меня как раз проблема, потому что до этого с деревьями не работал, только со списками. А там все несколько проще. Если бы Вы могли мне каким-либо образом помочь с построением б. дерева по нужному мне алгоритму, было бы очень хорошо.
0
|
26.05.2009, 23:39 | 4 |
Если ты никогда не работал с деревьями, то лучше почитай литературу, потому как на форуме я просто опухну столько объяснять. Насколько я понял, алгоритм построения дерева ты знаешь (т.е. карандашом на листочке нарисовать сможешь), так что больших проблем у тебя вызвать не должно.
Либо жди, вдруг объявится добрая душа, которая по твоему описанию напишет программу. Но, подозреваю, что у людей будет проблема, чтобы понять твой алгоритм. Я, например, при беглом прочтении не понял. Уровень задачи и тот факт, что способ её решения в теории ты понимешь, подсказывает мне то, что в жизни ты всё-таки собираешься заниматься программированием, а потому всё-таки порекомендовал бы тебе разобраться самому. Ну и если будут конкретные вопросы, то чем сможем поможем
0
|
26 / 26 / 9
Регистрация: 25.05.2009
Сообщений: 98
|
|
27.05.2009, 18:52 [ТС] | 5 |
Ну, на самом деле основной вопрос был: стоит ли заморачиваться с бинарными деревьями для такой задачи. Суть задачи проста - отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
В качестве алгоритма решения преподавателем был задан следующий: Пункты обхода последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута. Однако, поскольку реализация такого алгоритма слишком проста, то было задано выбирать не один, а два города, путь в которые наиболее выгоден. Соответственно получается не 1 а 2^(n-1) маршрутов, среди которых надо потом выбрать минимальный. Принцип построения бинарного дерева я понял (все оказалось проще, чем я думал), однако, как адаптировать его под запоминание таких маршрутов, я пока представить не могу. Возможно, есть более оптимальный путь решения, чем через бинарное дерево. Если у вас есть идеи по поводу того, как можно было бы решить эту задачу, прошу изложить их здесь.
0
|
27.05.2009, 19:34 | 6 |
Ну это уже скорее вопрос по алгоритмам, а с математикой у меня совсем плохо
Попробуй в этом разделе спросить https://www.cyberforum.ru/algorithms
1
|
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
|
|
28.05.2009, 20:14 | 7 |
привет всем!помогите пожалуйста!мне надо га си++ написать программу, кторая при вводе какогото арифмитического действия выдает как бы дерево разложения. например (х+5)*(3-(а-8)) и надо чтоб получилось * дальше 2 стрелочки в одной плюс (и из нее отходит опять 2 стрелочки в одной 5 в другой х, вот ) а в другой минус потом из нее 2 стрелочки в одной а в другой минус от нее еще 2 стрелочки в одной а в другой 8, ну короче разложение такое!!подалуйста!!очень надо!!!!!!за деньги, аська 44333649пример
* /\ + - / \ /\ а 5 2 * / \ а - /\ у 6 Добавлено через 1 минуту 39 секунд привет всем!помогите пожалуйста!мне надо га си++ написать программу, кторая при вводе какогото арифмитического действия выдает как бы дерево разложения. например (х+5)*(3-(а-8)) и надо чтоб получилось * дальше 2 стрелочки в одной плюс (и из нее отходит опять 2 стрелочки в одной 5 в другой х, вот ) а в другой минус потом из нее 2 стрелочки в одной а в другой минус от нее еще 2 стрелочки в одной а в другой 8, ну короче разложение такое!!подалуйста!!очень надо!!!!!!за деньги, аська 44333649пример * /\ + - / \ /\ а 5 2 * / \ а - /\ у 6 Добавлено через 1 минуту 11 секунд блин, дерево не получается нормалньо нариосвать ну вобщем смысл понятен я надеюсь, пожалуйста, очень прошу, помогите!!
0
|
29.05.2009, 11:04 | 8 |
Представление выражения в двоичном дереве
Посты #3 и #5
0
|
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
|
|
29.05.2009, 23:44 | 9 |
C++ Builder на этом языке желаетльно..(
0
|
30.05.2009, 11:51 | 10 |
https://www.cyberforum.ru/cpp-... 37065.html
Скажем так. Тебе выдали программу, которая уже делает все самые сложные действия, а так же умеет печатать дерево (пусть и не так карасиво, как требует того задание). Причём программу выдали тебе совершенно бесплатно. Вот хватай её и ищи того, кто заденьги тебе доработает её напильником. Поискать можешь, например, здесь https://www.cyberforum.ru/order-program При этом не забудь указать свою версию builder'а, чтобы в дальнейшем не возникло конфуза
0
|
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
|
|
30.05.2009, 16:23 | 11 |
а вы можете ща деньги??
0
|
30.05.2009, 16:26 | 12 |
На семнадцатой итерации чтения вопроса у меня переполнился стек. Но тем не менее буду как наш депутат, заявивший "я книгу не читал, но с автором не солгласен", и отвечу "нет"
0
|
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
|
|
30.05.2009, 16:26 | 13 |
вы можете за деньги?
0
|
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
|
||||||
30.05.2009, 17:03 | 15 | |||||
0
|
30.05.2009, 18:07 | 16 |
Это программа перевода выражения в так называемую польскую запись. С такой формой можно строить код по вычислению выражения, но неудобно "рисовать" дерево выражения (особенно в текстовом режиме). Хотя с него можно и рисовать, только код получается более геморройный, чем с дерева
0
|
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
|
|
30.05.2009, 18:16 | 17 |
ну так если я введу выраженпие какоето, мне программа выдаст дерево?
0
|
30.05.2009, 18:26 | 18 |
нет. Если ты введёшь "(a+b)*(c-d)", то программа тебе выдаст "ab+cd-*" или что-то типа того. Чтобы выражение разрисовать в виде дерева в консоли, нужно мудохаться, потому как дерево за один проход нормально не распечатать.
0
|
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
|
|
30.05.2009, 18:47 | 19 |
так а можно эту программу както оттредактировать чтоб она дерево выдавала?
0
|
30.05.2009, 18:56 | 20 |
Можно. Но долго, муторно и геморно
0
|
30.05.2009, 18:56 | |
30.05.2009, 18:56 | |
Помогаю со студенческими работами здесь
20
Построение бинарного дерева. Где ошибка? Код Хаффмана реализованный через построение бинарного дерева Построение иерархического дерева из двумерного массива Построение бинарного дерева. Обход дерева Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |