Форум программистов, компьютерный форум CyberForum.ru

Алгоритм поиска элемента последовательности, не являющегося элементом второй - C++

Восстановить пароль Регистрация
 
Stranger65536
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 8
27.04.2013, 22:53     Алгоритм поиска элемента последовательности, не являющегося элементом второй #1
Доброго времени суток! Выполняя очередную лабораторную по программированию, наткнулся на проблему выбора наиболее быстрого алгоритма для решения поставленной задачи.

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

C++
1
2
3
a a a a a of in It of is in so of in of by in He in In of of of in The has one the the has the are six two and The has big and old and You can see old You can the was who the the the the men and and the and and lot the copy book that that more than They very both new. they keep also find some made many have read very Son' time every there books books books which glass there first books lived first other spent Museum world. there. nearly papers daily. Museum cases. Caxton Museum famous writer author 'David books, Museum British largest printed English million receive British Library printed English printed Caxton. printer British Charles popular English 'Oliver Twist', 'Dombey British thousand century. England. studied. Dickens, Library. libraries language, fifteenth collection beautifully illustrated manuscripts manuscripts, reading-room Copperfield', printing-press
 
9 a a on of of in is is of It is in It is to go up to So is 23 It is 14 is to of of is is He to he in we is of it is by The big the the Big But Big Ben the the the The 318 You 374 the the the the But its fit The Its two The The Big Ben Sir had the job see the was put up. Sir was big One day the St. St. the the But for not Big Now the all the Ben. bell bell 13.5 feet have top. from face feet only just into some feet that bags feet bell that bell man. said call bell name said "Why call bell over that clock tower often clock tons. clock tower high. steps reach clock looks small below wide. would long. equal coal. long. clock after Hall. joke, Ben?" known world name. Palace London called really clock. weighs tower. weight called "Shall tower. biggest someone Britain. pavement Benjamin Benjamin hour-hand Stephen's Westminster classrooms. minute-hand Parliament, Stephen's?"
Правильный ответ: so

Вариант последовательного перебора всех элементов первой последовательности и для каждого из них перебора всех элементов второй последовательности не предлагать O(n * m) слишком долго. Страшных алгоритмов и структур хранения не боюсь).

P.S. последовательности хранятся в std::set
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2013, 22:53     Алгоритм поиска элемента последовательности, не являющегося элементом второй
Посмотрите здесь:

C++ Найти сумму элементов последовательности, начиная от первого отрицательного элемента и до конца последовательности.
Даны две последовательности.Верно ли, что все числа второй последовательности входят в первую. C++
C++ В программе написать функции: вставки элемента, поиска максимального элемента, определения среднего арифметического элементов массива
C++ Удаление максимального элемента из списка с предыдущим элементом
Перед каждым положительным элементом массива вставить элемент с нулевым значением, перезаписать эти элементы во второй массив C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
27.04.2013, 23:15     Алгоритм поиска элемента последовательности, не являющегося элементом второй #2
Сделайте вектор хранящий set<string> разных длин.
Что-то вроде такого:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
set<string> len1 = {"a", "b", "c"};
set<string> len2 = {"so", "bo", "mm"};
set<string> len3 = {"air"};
set<string> len4 = {"hair"};
set<string> len5 = {"books"};
set<string> len6 = {"phrase", "pillow", "habbit"};
vector<set<string>> vec1;
vec1.push_back(len1);
vec1.push_back(len2);
vec1.push_back(len3);
vec1.push_back(len4);
vec1.push_back(len5);
vec1.push_back(len6);
//и аналогично для второй последовательности
Индекс вектора + 1 дает понятие о строках хранящихся в данном множестве.
И потом обычным поиском(find) ищите различные элементы, соблюдая параметр длины.
Можно, конечно, держать всё в одном наборе и хранить индексы где изменяются длины строк, но при добавлении новой строк уйдет уйма времени на восстановление индексов.
Stranger65536
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 8
27.04.2013, 23:21  [ТС]     Алгоритм поиска элемента последовательности, не являющегося элементом второй #3
Но ведь мы потратим в лучшем случае O(n + m) времени на формирование этих векторов, а потом еще (N + M)log(size+N+M). на добавление этого всего в set. Потом поиск займет еще O(n + m) времени.
Это конечно быстрее, но как-то черезчур...
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
27.04.2013, 23:25     Алгоритм поиска элемента последовательности, не являющегося элементом второй #4
Если сразу вставлять строки куда надо, а не в один сет и потом разбирать его по полкам, то должно быть неплохо. Хотя придется код переписывать...
Подождите еще. Может у кого-то появится идея получше
Stranger65536
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 8
27.04.2013, 23:32  [ТС]     Алгоритм поиска элемента последовательности, не являющегося элементом второй #5
переписать код на вариант, когда строки будут автоматически добавляться, будет недолго
что-то в духе
C++
1
2
3
4
5
6
7
vector<set<string>> v;
while (in.good()) {
    /*
        чтение s
    */
    v[s.length()].insert(s);
}
но все равно асимптотика явно не лучшая...Ладно, подождем лучших идей
Yandex
Объявления
27.04.2013, 23:32     Алгоритм поиска элемента последовательности, не являющегося элементом второй
Ответ Создать тему
Опции темы

Текущее время: 08:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru