Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Поиск максимального размера подпоследовательности 
:(
    Опции темы
mes
Дата 10.7.2011, 09:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


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

Репутация: 144
Всего: 250



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

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



--------------------
PM MAIL WWW   Вверх
volatile
Дата 10.7.2011, 10:12 (ссылка) |    (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 37
Всего: 85



Цитата(Сыроежка @  9.7.2011,  20:21 Найти цитируемый пост)
Если я ничего не напутал, то получился изящный профессионально написанный алгоритм

Вы все напутали. Получился уродливый, дилетанский, и не работающий алгоритм.
Можете убедиться сами. (вызывал по вашей инструкции с 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 не нужен
все делается гораздо проще.
Код

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/57c997ad7091...3fbafba2c05d295
И кстати, легко переделывается на алгоритм возвращающий не длину, а итератор.
Последнее делать не стал. Это вам домашнее задание.   smile 

PM MAIL   Вверх
Сыроежка
Дата 10.7.2011, 15:37 (ссылка)    | (голосов:4) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

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



Цитата(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. Ну и где в вашей последовательности хотя бы два равных элемента?!

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

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

Это кто же вас таким непорядочным воспитал?!!!
PM MAIL   Вверх
volatile
Дата 10.7.2011, 17:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 37
Всего: 85



Цитата(Сыроежка @  10.7.2011,  15:37 Найти цитируемый пост)
int arr[] = { 1, 3, 4, 2, 7, 8, 9 };
Алгоритм правильно выдал, что результат равен 0. Что вас не устраивает?! Какой вы ждали результат?! Похоже, вы просто не понимапете, о чем идет речь! Вы же сами задали предикат std::equal_to. Ну и где в вашей последовательности хотя бы два равных элемента?!

Кнечно-же я ничего не понимаю!  smile  Поэтому по глупости подумал, что условие задания, данное вами-же должно выполняться:
Цитата(Сыроежка @ 7.7.2011,  18:04)
На одном форуме встретил такое задание для студентов: найти размер максимальной подпоследовательности, элементы которой возрастают по значению. То есть чтобы было понятно, то, например, если дан массив
Код

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

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

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

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

Можно даже сказать я буквально спер у вас весь код!  smile 
Цитата(Сыроежка @  10.7.2011,  15:37 Найти цитируемый пост)
в отличии от вашего первоначльного страшного кода

У вас галлюцинации? или вы все еще про  p = (int*)((char*) p + 3); ?
Цитата(Сыроежка @  10.7.2011,  15:37 Найти цитируемый пост)
Вы полностью повторили то, что я говорил

Насколько же вы гениальны! Удивляюсь только почуме вы сами не смогли повторить то о чем говорили. smile 
Цитата(Сыроежка @  10.7.2011,  15:37 Найти цитируемый пост)
Это кто же вас таким непорядочным воспитал?!!! 

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

Впрочем наверное действительно нужно вас пожалеть...
PM MAIL   Вверх
mes
Дата 10.7.2011, 17:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


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

Репутация: 144
Всего: 250



Цитата(Сыроежка @  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 Найти цитируемый пост)
У вас крайне плохие человеческие качества! 

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

Цитата(Сыроежка @  10.7.2011,  14:37 Найти цитируемый пост)
Это кто же вас таким непорядочным воспитал?!!! 

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




--------------------
PM MAIL WWW   Вверх
Сыроежка
Дата 10.7.2011, 20:25 (ссылка)    | (голосов:4) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

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



Цитата(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 Найти цитируемый пост)
И проблема состоит в том, что без написания собственного алгоритма для поиска диапазона упорядоченнных смежных элементов, эту проблему не решить.



Вы хоть бы откровенно так не лгали! Зотя бы сами себя уважали!
PM MAIL   Вверх
volatile
Дата 10.7.2011, 20:48 (ссылка) |    (голосов:5) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 37
Всего: 85



Цитата(Сыроежка @  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 Найти цитируемый пост)
Это кто же вас таким непорядочным воспитал?!!! 

 smile

Добавлено через 3 минуты и 48 секунд
Это оставшиеся в наличии аргументы знатока от стандартов С/С++
PM MAIL   Вверх
Earnest
Дата 11.7.2011, 07:16 (ссылка) |    (голосов:3) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183



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

 


--------------------
...
PM   Вверх
xvr
Дата 11.7.2011, 14:31 (ссылка) |    (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

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



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

PM MAIL   Вверх
RastaDja
Дата 11.7.2011, 15:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



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

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


--------------------
The more closely you look at one thing, the less closely can you see something else.
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn

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


 




[ Время генерации скрипта: 0.0995 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.