Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C++ Builder > Вычисления в массиве.


Автор: Flynn 10.12.2006, 22:05
 Дописываю программу написанную другим "программистом". Причем для этого программиста было явной тайно существование классов и шаблонов, уже задолбался разбираться с бесконечными массивами и переменными судя по названию которых их назначение известно только одному автору.

 Но собственно сейчас проблема в том, что сейчас застрял на одной функции. Суть ее состоит вот в чем:
Есть матрица, где первым значением каждой строки является ID элемента, вторым - число связей этого элемента с остальными элементами (элементами чегото вроде сети состоящей из элементов и связей между этими элементами), ну а дальше собственно идет непосредственно ID самих связей по которым непосредственно и определяется, что с чем связано. И задано первый и последний элемент сети, ну и нужно найти все возможные варианты "пути" от первого до последнего и занести их все в другой массив. 

 И я собственно застрял на том, как найти все возможные эти пути, проблема состоит в том что просчитать один без проблем, но из каждого элемента может быть 1 или более связей с какимто другим(и) элементами т.е. количество возможностей может возрасти с каждым новым элементом на пути от первого до последнего и как все это просчитать не пойму.     

 Уже просто мозг отказывает, и так переписал по новой примерно 800 строк кода, а эту функцию ох как не хочется заново переделывать, хотел просто дописать недостающий кусок кода но уперся в стену smile. Поэтому прошу помощи хотябы алгоритмом, но лучше кодом..

Автор: ABW 11.12.2006, 00:06
А может оказаться такая ситуация, что элементы связаны по кругу, т.е. число возможных вариантов пути бесконечно? (если есть хотя бы 1 цикл, решений будет бесконечность)

А так делается это при помощи рекурсии. 

Кстати даже если бы это был класс, то без рекурсии тоже никак.

Всё же не поще свой класс написать?

Автор: Flynn 11.12.2006, 00:12
Цитата(ABW @ 11.12.2006,  00:06)
А может оказаться такая ситуация, что элементы связаны по кругу, т.е. число возможных вариантов пути бесконечно?

Нет такова быть неможет. 

Цитата(ABW @ 11.12.2006,  00:06)
Всё же не проще свой класс написать?

 Чтобы всю эту помойку внести в класс нужно переписывать уйму кода т.к. стиль написания поражает, а попытки использования полиморфизма показали, что проще переписать всю программу с нуля.

Меня просто вгоняет в тоску эта функция. О рекурсии я подумал уже, но суть в том, что там неизвестно вообще сколько раз будет вызываться данная функция, причем необходимо сделать так, чтобы каждый раз прощитывались разные варианты пути, которые могут имет отличия в любом месте.  smile 

Автор: ABW 11.12.2006, 00:18
Поищи в инете что такое рекурсия, если будут вопросы - то пиши.
(Рекурсия - это когда функция вызывает сама себя.)

Тебе надо получить, фактически, массив строк ,в каждой из которых находится список пройденных точек?

Автор: Flynn 11.12.2006, 06:56
Цитата(ABW @ 11.12.2006,  00:18)
Тебе надо получить, фактически, массив строк ,в каждой из которых находится список пройденных точек?

Да. Именно это мне и нужно сделать.

Автор: Bima 11.12.2006, 08:27
Напиши исходные данные здесь. Какой начальный массив, какой конечный, для примера что на выходе должны иметь и как заполняется исходный массив. Чем подробнее напишь, тем легче будет реализация

Автор: ABW 11.12.2006, 12:14
Цитата(Bima @  11.12.2006,  08:27 Найти цитируемый пост)
Напиши исходные данные здесь. Какой начальный массив, какой конечный, для примера что на выходе должны иметь и как заполняется исходный массив. Чем подробнее напишь, тем легче будет реализация
Да, напиши об этом, т.к. есть неплохая идея. (луше вряд ли я найду)

Автор: pandrew 11.12.2006, 16:13
Цитата(Flynn)
Есть матрица, где первым значением каждой строки является ID элемента, вторым - число связей этого элемента с остальными элементами (элементами чегото вроде сети состоящей из элементов и связей между этими элементами), ну а дальше собственно идет непосредственно ID самих связей по которым непосредственно и определяется, что с чем связано. И задано первый и последний элемент сети, ну и нужно найти все возможные варианты "пути" от первого до последнего и занести их все в другой массив. 

Судя по твоему описанию, твой предшественник описал с помощью матрицы (массива, списка) (не)ориентированный граф и стоит задача вывести все возможные пути из одной вершины в другую.
Алгоритм решения (разные варианты)  можно взять из книжки "алгоритмы на графах". Дабы адаптировать твою "матрицу" к книжному алгоритму возможно потребуется завести класс-адаптер, т.е. класс вмещающий "матрицу" и предоставляющий методы доступа к вершинам, ребрам графа и отметки о прохождении.

Автор: ABW 12.12.2006, 09:57
А по-моему нужна коротенькая рекурсивная функция и одна глобальная переменная типа AnsiString. И всё. Проблема будет решена.

Автор: Anikmar 12.12.2006, 15:35
Одной глобальной нельзя - надо найти ВСЕ пути от одного узла к другому - по сути типа сетевой задачи.
Функция может быть типа такой:
bool IsLink(Point1, Point2) 
Должна возвращать истину, если между узлом Point1 и узлом Point2 есть путь. Соответственно внутри она берет все узлы, на которые у нее есть связи и каждый по очереди проверяет при помощи рекурсии...

А в головной функции берем исходный узел, конечный узел, и для всех узлов, прикрепленных к исходному вызываем енто чудо... - если путь есть, добавляем орчередную строчку к результату.

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

Это так, общая идея, каким путем можно идти. 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)