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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Krios
0 / 0 / 0
Регистрация: 12.10.2009
Сообщений: 10
#1

Поиск самой длинной неубывающей подпоследовательности - C++

12.10.2009, 19:25. Просмотров 1151. Ответов 5
Метки нет (Все метки)

Формулировка задачи: Реализовать на языке C или C++ алгоритм поиска для заданной числовой последовательности самой длинной неубывающей подпоследовательности.

Хотелось бы увидеть код или хотя бы фрагменты, но если объясните алгоритм на словах, буду тоже благодарен!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.10.2009, 19:25     Поиск самой длинной неубывающей подпоследовательности
Посмотрите здесь:

C++ подсчёт количества членов в наиболее длинной подпоследовательности из одинаковых чисел
Поиск самой длинной строки в файле C++
C++ Переделать функцию поиска самой длинной строки так, чтобы она правильно печатала размер произвольно длинной входной строки и воспроизводила ее
Определить длину самой упорядоченной по возрастанию подпоследовательности соседних элементов C++
C++ Поиск самой длинной строки в const char**
C++ Функция нахождения самой длинной неубывающей подпослед-ти
C++ Функция нахождения самой длинной неубывающей подпоследовательности
Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. C++
C++ Определить количество чисел в наиболее длинной подпоследовательности из нулей
C++ Найти длину самой длинной возрастающей подпоследовательности в массиве
C++ Поиск самой длинной цепочки из подряд идущих одинаковых элементов в массиве
C++ Поиск максимальной по длине монотонно неубывающей подпоследовательности вещественных чисел

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ketino
8 / 8 / 0
Регистрация: 21.09.2009
Сообщений: 84
12.10.2009, 19:43     Поиск самой длинной неубывающей подпоследовательности #2
Цитата Сообщение от Krios Посмотреть сообщение
Формулировка задачи: Реализовать на языке C или C++ алгоритм поиска для заданной числовой последовательности самой длинной неубывающей подпоследовательности.

Хотелось бы увидеть код или хотя бы фрагменты, но если объясните алгоритм на словах, буду тоже благодарен!
На словах:
Пусть есть массив М длинной D чисел.
Переменная Н будет хранить индекс первого числа искомой последовательности, К - последний индекс.
Переменная НВР и КВР - начало и конец текущей последовательности
Алгоритм:
C++
1
2
3
4
5
6
7
8
9
H=K=HBP=KBP=1;
for (i=2;i<= D;i++) {
  if M[i-1]<=M[i] {
     KBP++;
  } else {
     if (KBP-HBP) > (K-H) {H=HBP; K=KBP;};
     HBP=KBP=i; 
  };
}
Krios
0 / 0 / 0
Регистрация: 12.10.2009
Сообщений: 10
15.10.2009, 12:05  [ТС]     Поиск самой длинной неубывающей подпоследовательности #3
Ketino написал алгоритм поиска самой длинной неубывающей подряд идущей подпоследовательности. А требуется найти просто самую длинную неубывающую подпоследовательность. Например, для 1 0 2 1 3 2 4 3 5 это будет 1 2 3 4 5 или 0 2 3 4 5...
Ketino
8 / 8 / 0
Регистрация: 21.09.2009
Сообщений: 84
15.10.2009, 12:13     Поиск самой длинной неубывающей подпоследовательности #4
Цитата Сообщение от Krios Посмотреть сообщение
Ketino написал алгоритм поиска самой длинной неубывающей подряд идущей подпоследовательности. А требуется найти просто самую длинную неубывающую подпоследовательность. Например, для 1 0 2 1 3 2 4 3 5 это будет 1 2 3 4 5 или 0 2 3 4 5...
Тогда эта задача для ветки "Алгоритмы", а не для начинающих С++
Krios
0 / 0 / 0
Регистрация: 12.10.2009
Сообщений: 10
15.10.2009, 12:50  [ТС]     Поиск самой длинной неубывающей подпоследовательности #5
Цитата Сообщение от Ketino Посмотреть сообщение
Тогда эта задача для ветки "Алгоритмы", а не для начинающих С++
Я сомневался куда отнести эту задачу, поэтому написал в "любые вопросы", а администрация форума определила её сюда.
Krios
0 / 0 / 0
Регистрация: 12.10.2009
Сообщений: 10
15.10.2009, 13:18  [ТС]     Поиск самой длинной неубывающей подпоследовательности #6
Цитата Сообщение от TanT Посмотреть сообщение
1. администрация форума всегда права
2. если администрация форума не права см. пункт 1. (с)
TanT, я не выражал недовольство по отношению к администрации. И уже создал эту тему в разделе "алгоритмы", так что вопрос исчерпан.
Yandex
Объявления
15.10.2009, 13:18     Поиск самой длинной неубывающей подпоследовательности
Ответ Создать тему
Опции темы

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