| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C++ Builder > Вычисления в массиве. |
| Автор: Flynn 10.12.2006, 22:05 |
| Дописываю программу написанную другим "программистом". Причем для этого программиста было явной тайно существование классов и шаблонов, уже задолбался разбираться с бесконечными массивами и переменными судя по названию которых их назначение известно только одному автору. Но собственно сейчас проблема в том, что сейчас застрял на одной функции. Суть ее состоит вот в чем: Есть матрица, где первым значением каждой строки является ID элемента, вторым - число связей этого элемента с остальными элементами (элементами чегото вроде сети состоящей из элементов и связей между этими элементами), ну а дальше собственно идет непосредственно ID самих связей по которым непосредственно и определяется, что с чем связано. И задано первый и последний элемент сети, ну и нужно найти все возможные варианты "пути" от первого до последнего и занести их все в другой массив. И я собственно застрял на том, как найти все возможные эти пути, проблема состоит в том что просчитать один без проблем, но из каждого элемента может быть 1 или более связей с какимто другим(и) элементами т.е. количество возможностей может возрасти с каждым новым элементом на пути от первого до последнего и как все это просчитать не пойму. Уже просто мозг отказывает, и так переписал по новой примерно 800 строк кода, а эту функцию ох как не хочется заново переделывать, хотел просто дописать недостающий кусок кода но уперся в стену |
| Автор: ABW 11.12.2006, 00:06 |
| А может оказаться такая ситуация, что элементы связаны по кругу, т.е. число возможных вариантов пути бесконечно? (если есть хотя бы 1 цикл, решений будет бесконечность) А так делается это при помощи рекурсии. Кстати даже если бы это был класс, то без рекурсии тоже никак. Всё же не поще свой класс написать? |
| Автор: Flynn 11.12.2006, 00:12 | ||||
Нет такова быть неможет.
Чтобы всю эту помойку внести в класс нужно переписывать уйму кода т.к. стиль написания поражает, а попытки использования полиморфизма показали, что проще переписать всю программу с нуля. Меня просто вгоняет в тоску эта функция. О рекурсии я подумал уже, но суть в том, что там неизвестно вообще сколько раз будет вызываться данная функция, причем необходимо сделать так, чтобы каждый раз прощитывались разные варианты пути, которые могут имет отличия в любом месте. |
| Автор: ABW 11.12.2006, 00:18 |
| Поищи в инете что такое рекурсия, если будут вопросы - то пиши. (Рекурсия - это когда функция вызывает сама себя.) Тебе надо получить, фактически, массив строк ,в каждой из которых находится список пройденных точек? |
| Автор: Flynn 11.12.2006, 06:56 | ||
Да. Именно это мне и нужно сделать. |
| Автор: Bima 11.12.2006, 08:27 |
| Напиши исходные данные здесь. Какой начальный массив, какой конечный, для примера что на выходе должны иметь и как заполняется исходный массив. Чем подробнее напишь, тем легче будет реализация |
| Автор: ABW 11.12.2006, 12:14 |
| Да, напиши об этом, т.к. есть неплохая идея. (луше вряд ли я найду) |
| Автор: pandrew 11.12.2006, 16:13 | ||
Судя по твоему описанию, твой предшественник описал с помощью матрицы (массива, списка) (не)ориентированный граф и стоит задача вывести все возможные пути из одной вершины в другую. Алгоритм решения (разные варианты) можно взять из книжки "алгоритмы на графах". Дабы адаптировать твою "матрицу" к книжному алгоритму возможно потребуется завести класс-адаптер, т.е. класс вмещающий "матрицу" и предоставляющий методы доступа к вершинам, ребрам графа и отметки о прохождении. |
| Автор: ABW 12.12.2006, 09:57 |
| А по-моему нужна коротенькая рекурсивная функция и одна глобальная переменная типа AnsiString. И всё. Проблема будет решена. |
| Автор: Anikmar 12.12.2006, 15:35 |
| Одной глобальной нельзя - надо найти ВСЕ пути от одного узла к другому - по сути типа сетевой задачи. Функция может быть типа такой: bool IsLink(Point1, Point2) Должна возвращать истину, если между узлом Point1 и узлом Point2 есть путь. Соответственно внутри она берет все узлы, на которые у нее есть связи и каждый по очереди проверяет при помощи рекурсии... А в головной функции берем исходный узел, конечный узел, и для всех узлов, прикрепленных к исходному вызываем енто чудо... - если путь есть, добавляем орчередную строчку к результату. Недостатки - если есть круговая зависимость, то быстро вылетит с ошибкой. Преимущества - весьма быстро, дешево, сердито и кода минимум. Это так, общая идея, каким путем можно идти. |