Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.137.218.215] |
|
Сообщ.
#1
,
|
|
|
Есть граф, элементы которого связаны по схеме:
Элементы - простые индексы от 0 до 6 включительно. Хочу перечислить всевозможные пути, например: 0, 1 0, 1, 2, 6, 5 0, 1, 2, 6, 5, 4 0, 5, 6, 4 .... У меня правильно перебирает только первый путь, но дальше выводятся пути из несвязанных элементов. Почему это происходит? Может кто поможет пофиксить? Уже пару дней бьюсь, не могу понять в чём причина такого поведения. void goElement( std::vector< std::vector< unsigned short > > &relationsArr, unsigned short goElementId, std::vector< unsigned short > visitedIndexesPathArr ) { printf( "\nВход в элемент: %i\n", goElementId ); // Проверяем пути для посещения - если имеются для текущего элемента: for ( unsigned short i = 0; i < relationsArr[ goElementId ].size(); i++ ) { printf( "\t> Возможный путь: %i для %i элемента", relationsArr[ goElementId ][ i ], goElementId ); bool notVisited = true; // Проверяем - не посещали ли мы relationsArr[ goElementId ][ i ] (возможный путь для посещения) уже в нашем пути for ( unsigned short i1 = 0; notVisited && ( i1 < visitedIndexesPathArr.size() ); i1++ ) if ( relationsArr[ goElementId ][ i ] == visitedIndexesPathArr[ i1 ] ) notVisited = false; if ( notVisited ) { printf( " - не посещён! Посещаем...\n" ); visitedIndexesPathArr.push_back( relationsArr[ goElementId ][ i ] ); // запоминаем его как посещённый goElement( relationsArr, relationsArr[ goElementId ][ i ], visitedIndexesPathArr ); // Посещаем следующий } else { printf( " - посещён\n" ); } } printf( "\t\tВсе посещены, финальный путь: " ); for ( unsigned short i2 = 0; i2 < visitedIndexesPathArr.size(); i2++ ) printf( "%i, ", visitedIndexesPathArr[ i2 ] ); printf( "\n" ); } int main() { std::vector< std::vector< unsigned short > > relationsArr { {1,5,6}, {0,2,6}, {1,3,6}, {2,4,6}, {3,5,6}, {0,4,6}, {0,1,2,3,4,5} }; std::vector< unsigned short > visitedIndexesPathArr; visitedIndexesPathArr.push_back( 0 ); goElement( relationsArr, 0, visitedIndexesPathArr ); } |
Сообщ.
#2
,
|
|
|
Цитата Black*Eternal @ Может кто поможет пофиксить? Фиксю Онлайн-тест тут. #include <iostream> #include <vector> #include <map> typedef std::vector<uint> PathType; typedef std::map<uint,bool> VisType; typedef std::map<uint,std::vector<uint>> RelType; void PrintPath(uint I, PathType P, VisType V, RelType R) { if (V.find(I) != V.end()) return; P.push_back(I); V[I]=true; for(const auto& x: P) std::cout << ":" << x; std::cout << std::endl; for(const auto& i: R[I]) PrintPath(i,P,V,R); } int main() { VisType Vis; PathType Path; RelType Rel = { {0,{1,5,6}}, {1,{0,2,6}}, {2,{1,3,6}}, {3,{2,4,6}}, {4,{3,5,6}}, {5,{0,4,6}}, {6,{0,1,2,3,4,5}} }; for(auto const& i:Rel) PrintPath(i.first,Path,Vis,Rel); } Добавлено Add: Программулина, вроде правильная, но не оптимальная. Вопрос ТС - а в чем "неоптимальность"? |
Сообщ.
#3
,
|
|
|
Цитата JoeUser @ Фиксю Блин, ничего себе. Вот это решение... Удивило, что оно настолько короткое. Сейчас буду разбираться, спасибо! По неоптимальности - очень интересный вопрос. Честно говоря, даже не представляю, в чём она не оптимальна? |
Сообщ.
#4
,
|
|
|
Цитата Black*Eternal @ По неоптимальности - очень интересный вопрос. Честно говоря, даже не представляю, в чём она не оптимальна? Проверку очередной вершины нужно делать не в теле функции, а до входа в нее. Экономим на вызовах |
Сообщ.
#5
,
|
|
|
Цитата JoeUser @ Экономим на вызовах Лучше бы ты сэкономил на передаче параметров в функцию. Сейчас ты вектора и мапы передаешь туда по значению, что приводит к копированию содержимого контейнеров во внутренюю переменную при каждом вызове функции и передаче туда контейнеров - это крайне неэффективно, надо по ссылке или хотя бы по указателю. |
Сообщ.
#6
,
|
|
|
Цитата KILLER @ Лучше бы ты сэкономил на передаче параметров в функцию. Сейчас ты вектора и мапы передаешь туда по значению, что приводит к копированию содержимого контейнеров во внутренюю переменную при каждом вызове функции и передаче туда контейнеров - это крайне неэффективно, надо по ссылке или хотя бы по указателю. Именно так и надо! Мне там нужны локальные копии! Попробуй свой совет осуществить и увидишь неработающий вариант. Учитель блин. |
Сообщ.
#7
,
|
|
|
Цитата JoeUser @ Попробуй свой совет осуществить и увидишь неработающий вариант. Учитель блин. Твой вариант: http://ideone.com/mYQlxh Твой измененый вариант: http://ideone.com/nGAher ЗЫЖ Цитата Учитель блин. |
Сообщ.
#8
,
|
|
|
На счет одного значения - согласен, но если все передавать по указателю или ссылке - будет не то.
Хотя, если уж по уму, ... тогда вообще нету смысла этот параметр использовать в функции, а просто сделать глобальную переменную (константу). |