Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Алгоритм нахождения последовательностей


Автор: triclosan 24.12.2008, 18:46
Пускай имеем строки "HE", "LI", "BE", "NE", "NA", "CA", "EU", "BI", "AC", "IN". Задача найти все ряды, подчиняющиеся условию: вторая бува первой строки должна совподать с первой буквой второй. Строки двухбуквенные, уникальные. В одном ряду встречаться одинаковые не должны. 

Пытаюсь рекурсивно обходить, и почему-то получаю дубли. Не пойму почему они появляются:

Код

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

const int elementsCount = 10; // количество двухбуквенных строк
const string tmpList[] = {"HE", "LI", "BE", "NE", "NA", "CA", "EU", "BI", "AC", "IN"}; 


vector<string> elementsList; // временное хранилище
char *xLine, *yLine; // массивы для хранения индексов


void init()
{
    elementsList.assign(tmpList,  tmpList + sizeof(tmpList) / sizeof(string) );

    xLine = new char[elementsCount];
    yLine = new char[elementsCount];

    string tmp;
    for(int i = 0; i < elementsCount; i++)
    {
        tmp = elementsList.at(i);
        xLine[i]=tmp.at(0);
        yLine[i]=tmp.at(1);
    }
}

void printLn(vector<int>& v)
{

    for(vector<int>::iterator it = v.begin(); it!=v.end(); ++it)
    {
        cout<<elementsList.at(*it).c_str()<<' ';
    }
    cout<<endl;

}

void findNext(vector<int> tmpV, int ind, bool not_branched = true)
{
    tmpV.push_back(ind);
    bool not_found = true;
    for(int i = 0; i < elementsCount; i++ )
    {
        if(yLine[ind]==xLine[i] && find(tmpV.begin(), tmpV.end(), i )==tmpV.end() )
        {
            
            findNext(tmpV, i, not_found /* если false значит разветвление */);
            not_found = false;
        }
    }
    
    if(not_found) // обход последовательности завершен.
    {
        printLn(tmpV);
        
        if(not_branched) // если не порождено разветвлением начинаем со следующей строки
        {
            int neww = tmpV.at(0)+1;
            if(neww<elementsCount)
            {
                vector<int>s;
                findNext(s, neww);
            }
        }
    }
}


int main(int argc, char* argv[])
{
    init(); 

    vector<int> s;
    findNext(s, 0);


    return 0;
}

Выдает:

HE EU 
LI IN NE EU 
BE EU 
NE EU 
NA AC CA 
CA AC 
EU 
BI IN NE EU 
AC CA 
IN NE EU 
IN NA AC CA 
BI IN NA AC CA 
AC CA 
IN NE EU 
IN NA AC CA 
LI IN NA AC CA 
BE EU 
NE EU 
NA AC CA 
CA AC 
EU 
BI IN NE EU 
AC CA 
IN NE EU 
IN NA AC CA 
BI IN NA AC CA 
AC CA 
IN NE EU 
IN NA AC CA 

Автор: xvr 24.12.2008, 19:33
Подозрительна проверка (и логика) в строке 61. Получается, что ВСЕ строки, найденные по первому слогу, стартуют поиск со следующего элемента. Похоже таких стартов набирается несколько штук на каждый слог.
Почему бы вместо этого просто не сделать цикл в main?
Код

int main(int argc, char* argv[])
{
    init(); 

   for(int i=0;i<elementsCount;++i)
    {
     vector<int> s;
     findNext(s, i);
    }

    return 0;
}
а строки 61-69 убрать

Автор: GoldFinch 24.12.2008, 19:58
я бы сначала решил задачу математически, а еще лучше поискал бы готовое решение, задача-то классическая

Автор: triclosan 25.12.2008, 17:08
Кто подскажет можно ли узнать количество всех возможных комбинаций, без полного перебора ?

Автор: 2p0i 25.12.2008, 19:40
Цитата(triclosan @  25.12.2008,  17:08 Найти цитируемый пост)
Кто подскажет можно ли узнать количество всех возможных комбинаций, без полного перебора ? 

Можно, например, уменьшить алгоритмическую сложность с факториальной до экспоненциальной, с помощью динамического программирования, сложность будет O(N*2^N), подойдет если N <= 20. А быстрее не знаю.

Автор: triclosan 26.12.2008, 03:45
Цитата(2p0i @ 25.12.2008,  19:40)
Можно, например, уменьшить алгоритмическую сложность с факториальной до экспоненциальной, с помощью динамического программирования, сложность будет O(N*2^N), подойдет если N <= 20. А быстрее не знаю.


В "боевой" задаче 97 отрезков :( .

Тем не менее можно немножко подробнее про динамическое программирование?

Добавлено через 1 минуту и 26 секунд
Цитата(xvr @  24.12.2008,  19:33 Найти цитируемый пост)
Почему бы вместо этого просто не сделать цикл в main?

Спасибо, то, что надо!

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