VPF::Алгоритм нахождения последовательностей

triclosan

Дата 24.12.2008, 18:46 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 515
Регистрация: 18.8.2006

Репутация: 1
Всего: 12

Пускай имеем строки "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

Это сообщение отредактировал(а) triclosan - 24.12.2008, 18:48

xvr

Дата 24.12.2008, 19:33 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Подозрительна проверка (и логика) в строке 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 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26

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

triclosan

Дата 25.12.2008, 17:08 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 515
Регистрация: 18.8.2006

Репутация: 1
Всего: 12

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

2p0i

Дата 25.12.2008, 19:40 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 45
Регистрация: 14.9.2007

Репутация: нет
Всего: 1

Цитата(triclosan @ 25.12.2008, 17:08

)

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

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

triclosan

Дата 26.12.2008, 03:45 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 515
Регистрация: 18.8.2006

Репутация: 1
Всего: 12

Цитата(2p0i @ 25.12.2008, 19:40)

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

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

Добавлено через 1 минуту и 26 секунд

Цитата(xvr @ 24.12.2008, 19:33

)

Почему бы вместо этого просто не сделать цикл в main?

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »