На одном форуме встретил такое задание для студентов: найти размер максимальной подпоследовательности, элементы которой возрастают по значению. То есть чтобы было понятно, то, например, если дан массив


то для него максимальной подпоследовательностью является { 2, 7, 8, 9 }, размер которой равен 4.

Любопытно, как решить эту простую задачу с помощью стандартныхъ алгоритмов? Естественно ее надо обобщить. 
Найти размер максимальной подпоследовательности, смежные элементы которой удовлетворяют некоторому предикату.
Кто-нибудь пытался решить эту задачу с помощью стандарнтных алгоритмов? У кого какие есть соображения?

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

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

бррр..     

mes, ну, не без того - описался (ударение поставьте сами), а затем воспользовался передовой технологией копипаста 

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

Это сообщение отредактировал(а) borisbn - 8.7.2011, 08:39

ну при состовлении такого хитрого предиката вполне возможно не заметить .. уж больно он хитрый получился... 
мне кажется только, что Вы зря мучались, так как для adjacent_find в стл есть свой подходящий предикат..   
правда абсолютно бесхитросный  : 
 http://liveworkspace.org/code/02f672d0356a...2bd3dedb0073cb1
 



Это сообщение отредактировал(а) mes - 8.7.2011, 11:04

mes, да, но в задании требовалось

и

да и цикл

уже не очень соответствует 


P.S. Критиковать всегда проще, чем предложить чего-нибудь  Вот я по простому пути и пошёл   

я не задание решал, а лишь показал что 

  


ага, меня просто сильно "напугал" предикат, поэтому и отвлекся на критику..

 

вообще-то это я про себя говорил 

Надо же, кто-то все-таки откликнулся!

Естественно, первое, что приходит в голову, это использовать два ключевых  шага. 
Первый - это вызов std::adjacent_find с предикатом, как, например,  std::greater<value_type>.

Примечение:


А затем во-втором шаге использовать std::find_if с отрицанием данного предиката, то есть использовать адаптер std::not1.

Я так и сделал, и у меня получился достаточно изящный пользовательский алгоритм.

Но проблема состоит в том, что этот алгоритм выдает не совсем то, что требуется. То есть, например, для последовательности



он выдаст значение 5, то есть включит в максимальную подпоследовательность всю последовательность, так как все элементы после первого больше по значению, чем первый элемент.

Ежели строго следовать заданию, то максимальная подпоследовательность - это всего лишь { 1, 3, 5 }, так как 2 уже расположена не по возрастанию после 5.

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

Еще хуже дело обстоит, когда мы знаем размер максимальной подпоследовательность и хотим ее получить по искомому размеру. Алгоритм std::search_n для этих целей не подходит, так как он вызывает предикат не для смежных элементов, чтобы их можно было сравнить, а лишь для текущего значения итератора и заданного константного значения.

Я  сегодня с утра посидел за компьютером и в конечном итоге состряпал 40 разновидностей алгоритма adjacent_find! В большинстве своем они представляют из себя некоторые адаптеры стандартных алгоритмов  При этом в этот набор не входят алгоритмы, которые ищут не просто первый элемент из смежных элементов в последовательности, а весь диапазон смежных элементов.

Спасибо. ВЫ своим кодом меня позабавили! Ваш код в десятки раз сложнее, чем условие задания.

Замечу лишь, что проще написать свой алгоритм



который будет вам возвращать диапазон смежных элементых, удовлетворяющих предикату, и использовать его в исходной задаче. Я так в конечном итоге и сделал.
Этот алгоритм пишется очень просто.

Что касается вашего кода, то лишь замечу, что код (раз уж речь зашла об алгоритмах)


    
можно заменить на выхов алгоритма std::copy


 




Это сообщение отредактировал(а) Сыроежка - 8.7.2011, 19:12

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

Я из интернет-кафе общаюсь. У меня сейчас под рукой ничего нет, включая шпаргалки. Поэтому сейчас на коленках что-то напишу, скорей всего с ошибками.
Я покажу вариант, когдла вычисляется размер максимальной подпоследовательности просто для элементов, которые являются смежными с первым (то есть сравнение других элементов происходит с первым элементом подпоследовательности)




Увы, у меня сейчас время закончится. Я вам скорей всего завтра приведу полный цикл. Просто интересно использование отрицание бинарного предиката для поиска конца последовательности.



Завтра весь код покажу. Он достаточно прост и изящен. А для решения задачи в строгом соответсвии с условием я просто, как уже отметил, написал свой алгоритм adjacent_ordered_range, вместо использования adjacent_find и find_if/ 

чего то Вы намутили ?! все нормально должен искать, так как сравнение идет соседних элементов, а не с первым.. 


а зачем загромаждать себя лишним not`ом ? или это иследовательский энтузиазм ?

Итак, на чем я остановился? Ранее я уже набрал

    


Здесь лишнее определение типа value_type. Оно не используется. Поэтому выкидываем его



Теперь продолжим



Если я ничего не напутал, то получился изящный профессионально написанный алгоритм. Можете этот алгоритм от Сыроежки положить в свою копилку алгоритмов. Если его запускать с адаптером std::equal_to, то действительно можно получить размер максимальной последовательности смежных элементов.

Однако, как я уже заметил выше, для адаптеров типа  std::greater или std::less мы получим не возрастающую или убывающую по значению последовательность смежных элементов, а последовательность смежных элементов, каждый элемент которой больше/меньше  первого элемента. Это не ошибка кода, а результат того, что есть два подхода. Либо смежными считать все эелементы, которые удовлетворяют предикату, когда первым аргументом при вызове предиката является значение первого элемента. Либо смежными считать последовательность, все элементы которой попарно удовлетворяют предикату.

И проблема состоит в том, что без написания собственного алгоритма для поиска диапазона упорядоченнных смежных элементов, эту проблему не решить.

Если написать такой алгоритм, то вышеприведенный алгоритм естественно сильно упрощается.

смежными вообще то являются соседние элементы..  и уже из смежных выбираются те которые удовлетворяют предикату.. 

Вы все напутали. Получился уродливый, дилетанский, и не работающий алгоритм.
Можете убедиться сами. (вызывал по вашей инструкции с std::equal_to )
Впрочем с другими предикатами, не лучше!
http://liveworkspace.org/code/87e82c0ffb58...0e1bf995112d3f3

И это 3 дня трудов и 40 написанных алгоритмов! Вы долго выбирали самый лучший ?!
Да ладно бы совершили синтаксическую ошибку. Это еще можно было бы как-то понять.

Зачем вообще здесь вызывается find_if ? все можно сделать без него.
Достаточно одного только adjacent_find.
std::not1( std::bind1st( binary_predicate, *p.first ) ) ); <- и c такой конструкцией вы искренне верите в изящество?

Скажу вам больше, там даже adjacent_find не нужен
все делается гораздо проще.

Не претедную на изящество или профессионализм, но по крайней мере алгоритм работет, и работает корректно c любыми предикатами:
greater - найти наибольшую длину возрастающей последовательности;
less  - убывающей;
greater_equal - НЕ убывающей;
less_equal - НЕ возрастающей;

Можете проверить здесь.
http://liveworkspace.org/code/57c997ad7091...3fbafba2c05d295
И кстати, легко переделывается на алгоритм возвращающий не длину, а итератор.
Последнее делать не стал. Это вам домашнее задание.    

Совершенно не понятно, что я именно напутал?! Вы привели пример последовательности, в которой нет ни одной пары равных элементов. 

int arr[] = { 1, 3, 4, 2, 7, 8, 9 };

Алгоритм правильно выдал, что результат равен 0. Что вас не устраивает?! Какой вы ждали результат?! Похоже, вы просто не понимапете, о чем идет речь! Вы же сами задали предикат std::equal_to. Ну и где в вашей последовательности хотя бы два равных элемента?!

Что касается вашего примера, который вы сделали только после того, как я поместил грамотно написанный алгоритм, в отличии от вашего первоначльного страшного кода, то вы как раз и сделали то, что я говорил, то есть что надо писать собственный алгоритм, так как с помощью стандратных алгоритмов эту задачу не решить.

У вас крайне плохие человеческие качества! Вы полностью повторили то, что я говорил, воспользовались моим примером, а теперь начинаете на меня катить, как говорится, баллоны.

Это кто же вас таким непорядочным воспитал?!!!

Кнечно-же я ничего не понимаю!    Поэтому по глупости подумал, что условие задания, данное вами-же должно выполняться:

Ага, ваш алгоритм вычисляет только длину повторяющейся последовательности?
Ну так логично было бы предположить что бы и длину НЕповторяющейся последовательности хотя-бы он вычислял, но увы...
http://liveworkspace.org/code/e116ef8bbb47...3164f3f9db4ebdc

Свой алгоритм я даже и не проверял на эту способность, но как только что оказалось, он выполняет абсолютно корректно и эти еще 2 предиката:.
equal_to - поиск макс. повторяющейся последовательности
not_equal_to - поиск макс. НЕповторяющейся последовательности
Причем код самого алгоритмя не менял. Работает даже то, что не тестировалось.
http://liveworkspace.org/code/926e86d04c7d...9bf57092a2a5abc
Из 6 предикатов у вас, же, с горем попалам работает 1. 

Можно даже сказать я буквально спер у вас весь код!   

У вас галлюцинации? или вы все еще про  p = (int*)((char*) p + 3); ?

Насколько же вы гениальны! Удивляюсь только почуме вы сами не смогли повторить то о чем говорили.  

Вы не пробовали задать такой вопрост себе?

Впрочем наверное действительно нужно вас пожалеть...

граммотный ? уж позвольте не согласиться.. 

т.е. все форумчане для Вас на одно лицо ?!


может быть после того, как Вы сделали выводы, по предостваленным ответам  ?


но зато можно более стандартно и экологично, чем сделали это Вы..


Уж не о себе ли это ? Самокритика это хорошо 


интересно было бы узнать 

У вас с головой все в порядке?!!! Вы ставите предикат std::equal_to. Как он по вашему должен вычислить длину не повторяющейся последовательности?! Вы вообще-то понимаете, что сами пишите?!

Я поражаюсь вашей способносни перевирать! Это типичная характеристика непорядочного человека. 
Я говорил, что с помощью стандартных алгоритмов нельзя решить эту задачу и говорил, что тчтобы решить эту задачу, надо написать собственный алгоритм.. Вы решили задачу с помощью стандартных алгоритмов?! Нет? Так в чем проблема.
Далее я привел алгоритм, как с помощью стандартных алгоритмов найти подпоследовательность, элементы которой удовлетворяют предикату, когда первым аргументом является значение первого элемента подпоследовательности. Что неправильно работает?

Вы, вообще-то, отвечайте за свои слова! Но, я думаю, это излишнийпризыв, так как непорядочных людей бессмысленно призывать к порядочности.

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


Ужас, что же вы занимаетесь ложью-то? Не стыдно. Почитайте самое первое мое сообщение!





 Я сразу же сказал, что решить с помощью стандартных алгоритмов нельзя эту задачу. И далее еще до ваших потуг я написал






Вы хоть бы откровенно так не лгали! Зотя бы сами себя уважали!

 

Добавлено через 3 минуты и 48 секунд
Это оставшиеся в наличии аргументы знатока от стандартов С/С++

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

 

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

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

Это сообщение отредактировал(а) RastaDja - 11.7.2011, 15:16