Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Поиск максимального размера подпоследовательности

Автор: Сыроежка 7.7.2011, 18:04

На одном форуме встретил такое задание для студентов: найти размер максимальной подпоследовательности, элементы которой возрастают по значению. То есть чтобы было понятно, то, например, если дан массив Код int a[] = { 1, 3, 4, 2, 7, 8, 9 }; то для него максимальной подпоследовательностью является { 2, 7, 8, 9 }, размер которой равен 4. Любопытно, как решить эту простую задачу с помощью стандартныхъ алгоритмов? Естественно ее надо обобщить.  Найти размер максимальной подпоследовательности, смежные элементы которой удовлетворяют некоторому предикату. Кто-нибудь пытался решить эту задачу с помощью стандарнтных алгоритмов? У кого какие есть соображения?

Автор: Сыроежка 7.7.2011, 19:44

И это еще не все. Допустим, вы каким-то образом с использованием стандартных алгоритмов нашли размер максимальной подпоследовательности, удовлетворяющей заданному критерию  в виду предиката.  Но как теперь имея размер извлечь саму подпоследовательность? Стандартный алгоритм std::search_n не подходит, так как он ищет подпоследовательность заданной длины для фиксированного значения. К тому же предикату не передаются смежные элементы последовательности, а передается лишь заданное значение и значение очередного элемента последовательности.

Автор: borisbn 7.7.2011, 22:28

оно, конечно, можно, но предикат получился такой монстроидальный, что лучше, честно говоря ручками сделать - понятней будет http://liveworkspace.org/code/83a72ae675f1b40847913e88f95215b9

Автор: mes 7.7.2011, 22:46

Цитата PridicatStorege  бррр..

Автор: borisbn 8.7.2011, 06:17

mes, ну, не без того - описался (ударение поставьте сами), а затем воспользовался передовой технологией копипаста  Кстати, там ошибище. Причём не описка, а именно в алгоритме. Переделывать не хочу. Лень

Автор: mes 8.7.2011, 09:14

Цитата(borisbn @  8.7.2011,  05:17 ) а затем воспользовался передовой технологией копипаста  ну при состовлении такого хитрого предиката вполне возможно не заметить .. уж больно он хитрый получился...  мне кажется только, что Вы зря мучались, так как для adjacent_find в стл есть свой подходящий предикат..    правда абсолютно бесхитросный  :  Код for (auto f = arr.begin(); f != arr.end(); ) {     auto  e = std::adjacent_find( f, arr.end(), std::greater<int>() );                if (e != arr.end()) ++e;              for (auto it = f; it != e; ++it )             std::cout << *it << " ";         std::cout << " : ";                       std::swap(f,e);                       }  http://liveworkspace.org/code/02f672d0356a3b1382bd3dedb0073cb1

Автор: borisbn 8.7.2011, 09:37

mes, да, но в задании требовалось Цитата(Сыроежка @  7.7.2011,  18:04 ) найти размер максимальной подпоследовательности и Цитата(Сыроежка @  7.7.2011,  19:44 ) Но как теперь имея размер извлечь саму подпоследовательность? да и цикл Цитата(mes @  8.7.2011,  09:14 ) for (auto f = arr.begin(); f != arr.end(); ) уже не очень соответствует  Цитата(Сыроежка @  7.7.2011,  18:04 ) Любопытно, как решить эту простую задачу с помощью стандартныхъ алгоритмов? P.S. Критиковать всегда проще, чем предложить чего-нибудь  Вот я по простому пути и пошёл

Автор: mes 8.7.2011, 10:29

Цитата(borisbn @  8.7.2011,  08:37 )  да, но в задании требовалось я не задание решал, а лишь показал что  Цитата(mes @  8.7.2011,  08:14 ) для adjacent_find в стл есть свой подходящий предикат    Цитата(borisbn @  8.7.2011,  08:37 )  Критиковать всегда проще,  ага, меня просто сильно "напугал" предикат, поэтому и отвлекся на критику..

Автор: borisbn 8.7.2011, 10:32

Цитата(mes @  8.7.2011,  10:29 ) Критиковать всегда проще,  вообще-то это я про себя говорил

Автор: Сыроежка 8.7.2011, 18:20

Надо же, кто-то все-таки откликнулся! Естественно, первое, что приходит в голову, это использовать два ключевых  шага.  Первый - это вызов std::adjacent_find с предикатом, как, например,  std::greater<value_type>. Примечение: Код  typedef typename std::iterator_traits<ForwardIterator>::value_type value_type А затем во-втором шаге использовать std::find_if с отрицанием данного предиката, то есть использовать адаптер std::not1. Я так и сделал, и у меня получился достаточно изящный пользовательский алгоритм. Но проблема состоит в том, что этот алгоритм выдает не совсем то, что требуется. То есть, например, для последовательности Код int a[] = { 1, 3, 5, 2, 6 };  он выдаст значение 5, то есть включит в максимальную подпоследовательность всю последовательность, так как все элементы после первого больше по значению, чем первый элемент. Ежели строго следовать заданию, то максимальная подпоследовательность - это всего лишь { 1, 3, 5 }, так как 2 уже расположена не по возрастанию после 5. То есть получается, что такую простую задачу с помощью существующего набора стандартных алгоритмов не решить.   Еще хуже дело обстоит, когда мы знаем размер максимальной подпоследовательность и хотим ее получить по искомому размеру. Алгоритм std::search_n для этих целей не подходит, так как он вызывает предикат не для смежных элементов, чтобы их можно было сравнить, а лишь для текущего значения итератора и заданного константного значения. Я  сегодня с утра посидел за компьютером и в конечном итоге состряпал 40 разновидностей алгоритма adjacent_find! В большинстве своем они представляют из себя некоторые адаптеры стандартных алгоритмов  При этом в этот набор не входят алгоритмы, которые ищут не просто первый элемент из смежных элементов в последовательности, а весь диапазон смежных элементов.

Автор: Сыроежка 8.7.2011, 19:11

Цитата(borisbn @  7.7.2011,  22:28 ) оно, конечно, можно, но предикат получился такой монстроидальный, что лучше, честно говоря ручками сделать - понятней будет http://liveworkspace.org/code/83a72ae675f1...7913e88f95215b9  Спасибо. ВЫ своим кодом меня позабавили! Ваш код в десятки раз сложнее, чем условие задания. Замечу лишь, что проще написать свой алгоритм Код template <typename ForwardIterator,                  typename BinaryPredicate> std::pair<ForwardIterator, ForwardIterator> adjacent_range( ForwardIterator first,                                                                                                    ForwardIterator last,                                                                                                    BinaryPredicate binary_predicate ); который будет вам возвращать диапазон смежных элементых, удовлетворяющих предикату, и использовать его в исходной задаче. Я так в конечном итоге и сделал. Этот алгоритм пишется очень просто. Что касается вашего кода, то лишь замечу, что код (раз уж речь зашла об алгоритмах) Код for ( int i = 0; i < a_count; i++ ) {    cout << arr[ i ] << " "; }  cout << endl;      можно заменить на выхов алгоритма std::copy Код std::copy( arr, arr + a_count, std::ostream_iterator<int>( std::cout, " " ) );

Автор: Qu1nt 8.7.2011, 19:18

Сыроежка, покажите же свою реализацию!

Автор: Сыроежка 8.7.2011, 19:36

Я из интернет-кафе общаюсь. У меня сейчас под рукой ничего нет, включая шпаргалки. Поэтому сейчас на коленках что-то напишу, скорей всего с ошибками. Я покажу вариант, когдла вычисляется размер максимальной подпоследовательности просто для элементов, которые являются смежными с первым (то есть сравнение других элементов происходит с первым элементом подпоследовательности) Код template <typename ForwardIterator,                  typename BinaryPredicate> typename std::iterator_traits<ForwardIterator>::difference_type max_adjacent_seq( ForwardIterator first,                                                                                                                                         ForwardIterator last,                                                                                                                                         BinaryPredicate binary_predicate ) {    typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;    difference_type max = 0;    std::pair<ForwardIterator, ForwardIterator> p;    for ( ; first != last; first = p.second )    {       p.first = std::adjacent_find( first, last, binary_predicate ); Увы, у меня сейчас время закончится. Я вам скорей всего завтра приведу полный цикл. Просто интересно использование отрицание бинарного предиката для поиска конца последовательности. Код std::not1( std::bind1st( binary_predicate, *p.first ) ) Завтра весь код покажу. Он достаточно прост и изящен. А для решения задачи в строгом соответсвии с условием я просто, как уже отметил, написал свой алгоритм adjacent_ordered_range, вместо использования adjacent_find и find_if/

Автор: mes 9.7.2011, 01:39

Цитата(Сыроежка @  8.7.2011,  17:20 ) он выдаст значение 5, то есть включит в максимальную подпоследовательность всю последовательность, так как все элементы после первого больше по значению, чем первый элемент. Ежели строго следовать заданию, то максимальная подпоследовательность - это всего лишь { 1, 3, 5 }, так как 2 уже расположена не по возрастанию после 5. То есть получается, что такую простую задачу с помощью существующего набора стандартных алгоритмов не решить.   чего то Вы намутили ?! все нормально должен искать, так как сравнение идет соседних элементов, а не с первым..  Цитата(Сыроежка @  8.7.2011,  18:36 )  Просто интересно использование отрицание бинарного предиката для поиска конца последовательности. а зачем загромаждать себя лишним not`ом ? или это иследовательский энтузиазм ?

Автор: Сыроежка 9.7.2011, 20:21

Итак, на чем я остановился? Ранее я уже набрал      Код template <typename ForwardIterator,           typename BinaryPredicate> typename std::iterator_traits<ForwardIterator>::difference_type max_adjacent_seq( ForwardIterator first,                                                                                   ForwardIterator last,                                                                                   BinaryPredicate binary_predicate ) {    typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;    difference_type max = 0;    std::pair<ForwardIterator, ForwardIterator> p;    for ( ; first != last; first = p.second )    {       p.first = std::adjacent_find( first, last, binary_predicate ); Здесь лишнее определение типа value_type. Оно не используется. Поэтому выкидываем его Код template <typename ForwardIterator,           typename BinaryPredicate> typename std::iterator_traits<ForwardIterator>::difference_type max_adjacent_seq( ForwardIterator first,                                                                                   ForwardIterator last,                                                                                   BinaryPredicate binary_predicate ) {    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;    difference_type max = 0;    std::pair<ForwardIterator, ForwardIterator> p;    for ( ; first != last; first = p.second )    {       p.first = std::adjacent_find( first, last, binary_predicate ); Теперь продолжим Код template <typename ForwardIterator,           typename BinaryPredicate> typename std::iterator_traits<ForwardIterator>::difference_type max_adjacent_seq( ForwardIterator first,                   ForwardIterator last,                   BinaryPredicate binary_predicate ) {    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;    difference_type max = 0;    std::pair<ForwardIterator, ForwardIterator> p;    for ( ; first != last; first = p.second )    {       p.first = std::adjacent_find( first, last, binary_predicate );       p.second = last;       if ( p.first != p.second )       {          ForwardIterator next = p.first;          p.second = std::find_if( ++next, p.second,                                                std::not1( std::bind1st( binary_predicate, *p.first ) ) );          difference_type size = std::distance( p.first, p.second );          if ( max < size ) max = size;       }    }    return ( max ); } Если я ничего не напутал, то получился изящный профессионально написанный алгоритм. Можете этот алгоритм от Сыроежки положить в свою копилку алгоритмов. Если его запускать с адаптером std::equal_to, то действительно можно получить размер максимальной последовательности смежных элементов. Однако, как я уже заметил выше, для адаптеров типа  std::greater или std::less мы получим не возрастающую или убывающую по значению последовательность смежных элементов, а последовательность смежных элементов, каждый элемент которой больше/меньше  первого элемента. Это не ошибка кода, а результат того, что есть два подхода. Либо смежными считать все эелементы, которые удовлетворяют предикату, когда первым аргументом при вызове предиката является значение первого элемента. Либо смежными считать последовательность, все элементы которой попарно удовлетворяют предикату. И проблема состоит в том, что без написания собственного алгоритма для поиска диапазона упорядоченнных смежных элементов, эту проблему не решить. Если написать такой алгоритм, то вышеприведенный алгоритм естественно сильно упрощается.

Автор: mes 10.7.2011, 09:10

Цитата(Сыроежка @  9.7.2011,  19:21 )  Либо смежными считать все эелементы, которые удовлетворяют предикату, когда первым аргументом при вызове предиката является значение первого элемента. Либо смежными считать последовательность, все элементы которой попарно удовлетворяют предикату. смежными вообще то являются соседние элементы..  и уже из смежных выбираются те которые удовлетворяют предикату..

Автор: volatile 10.7.2011, 10:12

Цитата(Сыроежка @  9.7.2011,  20:21 ) Если я ничего не напутал, то получился изящный профессионально написанный алгоритм Вы все напутали. Получился уродливый, дилетанский, и не работающий алгоритм. Можете убедиться сами. (вызывал по вашей инструкции с std::equal_to ) Впрочем с другими предикатами, не лучше! http://liveworkspace.org/code/87e82c0ffb58f82210e1bf995112d3f3 И это 3 дня трудов и 40 написанных алгоритмов! Вы долго выбирали самый лучший ?! Да ладно бы совершили синтаксическую ошибку. Это еще можно было бы как-то понять. Зачем вообще здесь вызывается find_if ? все можно сделать без него. Достаточно одного только adjacent_find. std::not1( std::bind1st( binary_predicate, *p.first ) ) ); <- и c такой конструкцией вы искренне верите в изящество? Скажу вам больше, там даже adjacent_find не нужен все делается гораздо проще. Код template <typename ForwardIterator,            typename BinaryPredicate> typename std::iterator_traits<ForwardIterator>::difference_type max_adjacent_seq( ForwardIterator first,                   ForwardIterator last,                   BinaryPredicate binary_predicate ) {    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;    difference_type counter = 0, max = 0;    for ( ForwardIterator prev; ( prev = first ) != last && ++first != last; )    {       binary_predicate ( * first, * prev) ? ++ counter : counter = 0;       if ( counter > max ) max = counter;    }    if ( max ) ++ max;    return max; } Не претедную на изящество или профессионализм, но по крайней мере алгоритм работет, и работает корректно c любыми предикатами: greater - найти наибольшую длину возрастающей последовательности; less  - убывающей; greater_equal - НЕ убывающей; less_equal - НЕ возрастающей; Можете проверить здесь. http://liveworkspace.org/code/57c997ad7091488603fbafba2c05d295 И кстати, легко переделывается на алгоритм возвращающий не длину, а итератор. Последнее делать не стал. Это вам домашнее задание.

Автор: Сыроежка 10.7.2011, 15:37

Цитата(volatile @  10.7.2011,  10:12 ) Вы все напутали. Получился уродливый, дилетанский, и не работающий алгоритм. Можете убедиться сами. (вызывал по вашей инструкции с std::equal_to ) Впрочем с другими предикатами, не лучше! http://liveworkspace.org/code/87e82c0ffb58...0e1bf995112d3f3 Совершенно не понятно, что я именно напутал?! Вы привели пример последовательности, в которой нет ни одной пары равных элементов.  int arr[] = { 1, 3, 4, 2, 7, 8, 9 }; Алгоритм правильно выдал, что результат равен 0. Что вас не устраивает?! Какой вы ждали результат?! Похоже, вы просто не понимапете, о чем идет речь! Вы же сами задали предикат std::equal_to. Ну и где в вашей последовательности хотя бы два равных элемента?! Что касается вашего примера, который вы сделали только после того, как я поместил грамотно написанный алгоритм, в отличии от вашего первоначльного страшного кода, то вы как раз и сделали то, что я говорил, то есть что надо писать собственный алгоритм, так как с помощью стандратных алгоритмов эту задачу не решить. У вас крайне плохие человеческие качества! Вы полностью повторили то, что я говорил, воспользовались моим примером, а теперь начинаете на меня катить, как говорится, баллоны. Это кто же вас таким непорядочным воспитал?!!!

Автор: volatile 10.7.2011, 17:52

Цитата(Сыроежка @  10.7.2011,  15:37 ) int arr[] = { 1, 3, 4, 2, 7, 8, 9 }; Алгоритм правильно выдал, что результат равен 0. Что вас не устраивает?! Какой вы ждали результат?! Похоже, вы просто не понимапете, о чем идет речь! Вы же сами задали предикат std::equal_to. Ну и где в вашей последовательности хотя бы два равных элемента?! Кнечно-же я ничего не понимаю!    Поэтому по глупости подумал, что условие задания, данное вами-же должно выполняться: Цитата(Сыроежка @ 7.7.2011,  18:04) На одном форуме встретил такое задание для студентов: найти размер максимальной подпоследовательности, элементы которой возрастают по значению. То есть чтобы было понятно, то, например, если дан массив Код int a[] = { 1, 3, 4, 2, 7, 8, 9 }; то для него максимальной подпоследовательностью является { 2, 7, 8, 9 }, размер которой равен 4. Ага, ваш алгоритм вычисляет только длину повторяющейся последовательности? Ну так логично было бы предположить что бы и длину НЕповторяющейся последовательности хотя-бы он вычислял, но увы... http://liveworkspace.org/code/e116ef8bbb47cea663164f3f9db4ebdc Свой алгоритм я даже и не проверял на эту способность, но как только что оказалось, он выполняет абсолютно корректно и эти еще 2 предиката:. equal_to - поиск макс. повторяющейся последовательности not_equal_to - поиск макс. НЕповторяющейся последовательности Причем код самого алгоритмя не менял. Работает даже то, что не тестировалось. http://liveworkspace.org/code/926e86d04c7dfa7a79bf57092a2a5abc Из 6 предикатов у вас, же, с горем попалам работает 1.  Цитата(Сыроежка @  10.7.2011,  15:37 ) Что касается вашего примера, который вы сделали только после того, как я поместил грамотно написанный алгоритм Можно даже сказать я буквально спер у вас весь код!    Цитата(Сыроежка @  10.7.2011,  15:37 ) в отличии от вашего первоначльного страшного кода У вас галлюцинации? или вы все еще про  p = (int*)((char*) p + 3); ? Цитата(Сыроежка @  10.7.2011,  15:37 ) Вы полностью повторили то, что я говорил Насколько же вы гениальны! Удивляюсь только почуме вы сами не смогли повторить то о чем говорили.   Цитата(Сыроежка @  10.7.2011,  15:37 ) Это кто же вас таким непорядочным воспитал?!!!  Вы не пробовали задать такой вопрост себе? Впрочем наверное действительно нужно вас пожалеть...

Автор: mes 10.7.2011, 17:54

Цитата(Сыроежка @  10.7.2011,  14:37 ) Что касается вашего примера, который вы сделали только после того, как я поместил грамотно написанный  граммотный ? уж позвольте не согласиться..  Цитата(Сыроежка @  10.7.2011,  14:37 ) , в отличии от вашего первоначльного страшного кода, т.е. все форумчане для Вас на одно лицо ?! Цитата(Сыроежка @  10.7.2011,  14:37 ) то вы как раз и сделали то, что я говорил, то есть что надо писать собственный алгоритм может быть после того, как Вы сделали выводы, по предостваленным ответам  ? Цитата(Сыроежка @  10.7.2011,  14:37 )  так как с помощью стандратных алгоритмов эту задачу не решить. но зато можно более стандартно и экологично, чем сделали это Вы.. Цитата(Сыроежка @  10.7.2011,  14:37 ) У вас крайне плохие человеческие качества!  Уж не о себе ли это ? Самокритика это хорошо  Цитата(Сыроежка @  10.7.2011,  14:37 ) Это кто же вас таким непорядочным воспитал?!!!  интересно было бы узнать

Автор: Сыроежка 10.7.2011, 20:25

Цитата(volatile @  10.7.2011,  17:52 ) Ага, ваш алгоритм вычисляет только длину повторяющейся последовательности? Ну так логично было бы предположить что бы и длину НЕповторяющейся последовательности хотя-бы он вычислял, но увы... У вас с головой все в порядке?!!! Вы ставите предикат std::equal_to. Как он по вашему должен вычислить длину не повторяющейся последовательности?! Вы вообще-то понимаете, что сами пишите?! Я поражаюсь вашей способносни перевирать! Это типичная характеристика непорядочного человека.  Я говорил, что с помощью стандартных алгоритмов нельзя решить эту задачу и говорил, что тчтобы решить эту задачу, надо написать собственный алгоритм.. Вы решили задачу с помощью стандартных алгоритмов?! Нет? Так в чем проблема. Далее я привел алгоритм, как с помощью стандартных алгоритмов найти подпоследовательность, элементы которой удовлетворяют предикату, когда первым аргументом является значение первого элемента подпоследовательности. Что неправильно работает? Вы, вообще-то, отвечайте за свои слова! Но, я думаю, это излишнийпризыв, так как непорядочных людей бессмысленно призывать к порядочности. Добавлено через 8 минут и 12 секунд Цитата(mes @  10.7.2011,  17:54 ) Цитата(Сыроежка @  10.7.2011,  14:37 Найти цитируемый пост) то вы как раз и сделали то, что я говорил, то есть что надо писать собственный алгоритм может быть после того, как Вы сделали выводы, по предостваленным ответам  ? Ужас, что же вы занимаетесь ложью-то? Не стыдно. Почитайте самое первое мое сообщение! Цитата(Сыроежка @  7.7.2011,  18:04 ) Любопытно, как решить эту простую задачу с помощью стандартныхъ алгоритмов? Естественно ее надо обобщить.  Цитата(Сыроежка @  7.7.2011,  18:04 ) Любопытно, как решить эту простую задачу с помощью стандартныхъ алгоритмов? Естественно ее надо обобщить.  Найти размер максимальной подпоследовательности, смежные элементы которой удовлетворяют некоторому предикату. Кто-нибудь пытался решить эту задачу с помощью стандарнтных алгоритмов? У кого какие есть соображения?   Я сразу же сказал, что решить с помощью стандартных алгоритмов нельзя эту задачу. И далее еще до ваших потуг я написал Цитата(Сыроежка @  8.7.2011,  18:20 ) То есть получается, что такую простую задачу с помощью существующего набора стандартных алгоритмов не решить.   Цитата(Сыроежка @  9.7.2011,  20:21 ) И проблема состоит в том, что без написания собственного алгоритма для поиска диапазона упорядоченнных смежных элементов, эту проблему не решить. Вы хоть бы откровенно так не лгали! Зотя бы сами себя уважали!

Автор: volatile 10.7.2011, 20:48

Цитата(Сыроежка @  10.7.2011,  20:25 ) Я поражаюсь вашей способносни перевирать!  Цитата(Сыроежка @  10.7.2011,  20:25 ) Это типичная характеристика непорядочного человека.  Цитата(Сыроежка @  10.7.2011,  20:25 ) Но, я думаю, это излишнийпризыв, так как непорядочных людей бессмысленно призывать к порядочности. Цитата(Сыроежка @  10.7.2011,  20:25 ) У вас с головой все в порядке?!!!  Цитата(Сыроежка @  10.7.2011,  20:25 ) Ужас, что же вы занимаетесь ложью-то?  Цитата(Сыроежка @  10.7.2011,  20:25 ) Вы хоть бы откровенно так не лгали!  Цитата(Сыроежка @  10.7.2011,  15:37 ) Это кто же вас таким непорядочным воспитал?!!!    Добавлено через 3 минуты и 48 секунд Это оставшиеся в наличии аргументы знатока от стандартов С/С++

Автор: Earnest 11.7.2011, 07:16

Модератор: Ребята, прекратите грызню. Сыроежка, ты бы лучше проф. аргументы приводил, а не оскорблениями бросался. Если считаешь, что код от volatile неправильно работает, приведи пример, где он не работает. А меряние этими вашими... ну, в общем, кто что первый написал - вообще детский сад.

Автор: xvr 11.7.2011, 14:31

У меня дежавю? Или все темы с участием Сыроежки заканчиваются наездами на участников?

Автор: RastaDja 11.7.2011, 15:14

Уже несколько дней читаю топики с Сыроежкой. Не могу дождатся новых. Забавно ... Может завести новый раздел форума... (для почитателей Сыроежки) LOL    ЗЫ: Сыроежка, ничего личного

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