|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
15.05.2012, 15:37 | #1 |
Регистрация: 15.05.2012
Сообщений: 5
|
Не могу понять никак условие, что именно требуется для входных даннных
Народ, есть задачка со следующим условием
Из точки А в точку В можно добраться несколькими маршрутами. Все возможные траектории представить в виде дерева, у которого на вершине пункт А, а лист дерева - пункт В. Дерево строится упорядоченное, т.е. ближайший пункт всегда , допустим, левая ветвь, а следующий ближайший пункт - правая ветвь. Дерево строим только двоичное. Определить в методах объекта с таким деревом: кратчайшее расстояние от любого из выбранных пунктов до другого пункта из, внесение нового пункта в маршруте, удаление некоторого пункта из маршрута (снегопады и т. п.), вывод на экран выбранной траектории и вывод всег7о дерева на экран. Весь возможный список городов, на основании которого строится дерево, должен быть создан и сохранен в файле. Вопросы: какие исходные данные необходимы для решения этой задачи? По сути дела, если мы строим двоичное дерево, то от любого выбранного узла до другого всегда существует только один путь. P.S.: Код не нужен, необходимо только понять с чем кушается это о условие и какие исходные данные необходимы. |
15.05.2012, 19:12 | #2 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
В той постановке, что приведена, путей бесконечно много, а объем дерева тоже бесконечно велик.
Пусть у нас есть 3 города: A, B и C. Возможны следующие пути из A в B: - A-B, - A-C-B, - A-C-A-B, - A-C-A-C-B, ... |
16.05.2012, 17:55 | #3 |
Регистрация: 15.05.2012
Сообщений: 5
|
Для 3х городов все понятно, как будет выглядеть двоичное дерево. А предположим у нас четыре города, A, B, C, D, соединенных по схеме (см. вложение). В таком случае имеем следующие траектории от А до В:
|
16.05.2012, 21:21 | #4 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Как строить дерево, как раз понятно - в условии об этом написано.
Непонятно другое - как его построить, т.к. оно бесконечно, в частности, содержит циклические участки. Кстати, при заданном алгоритме построения и бесконечности самого дерева оно может не содержать листьев. Вообще. И это другая проблема. |
16.05.2012, 21:30 | #5 |
Регистрация: 15.05.2012
Сообщений: 5
|
В общем я не буду париьься с этими маршрутами. просто буду для каждого заданнооо маршрута строить свое упорядоченное бинарное дерево. а там уже буду выбирать, какой маршрут. что и с ним делать и т.д.
Спасиб за совет |
22.05.2012, 20:46 | #6 |
Регистрация: 15.05.2012
Сообщений: 5
|
Написал прогу. Строится бинарное дерево. Есть повторяющиеся узлы, но подсчет расстояний и т.п. вел с помощью матрицы смежности.
ЗЫ: препод остался доволен за такое нестандартное решение задачи ЗЗЫ: все условия задачи были соблюдены Тему считаем закрытой |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
В чём ошибка..никак не могу понять | Лися | Общие вопросы по Java, Java SE, Kotlin | 1 | 16.10.2011 00:50 |
Векторы, никак не могу понять | YourLastSong | Общие вопросы C/C++ | 6 | 26.12.2010 18:00 |
Не получается отсортировать структуру. В чем проблема понять никак не могу | AlEnanechker | Помощь студентам | 1 | 25.12.2009 17:02 |
Помогите, не могу понять, как объяснить программе, что именно я от нее хочу | Dead Romantic | Общие вопросы C/C++ | 4 | 03.12.2009 21:51 |
Не могу понять, что требуется? | Shuraken | Общие вопросы Delphi | 2 | 10.08.2007 11:41 |