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

@Krios · Регистрация: 12.10.2009

Author24 — интернет-сервис помощи студентам

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

Хотелось бы увидеть код или хотя бы фрагменты, но если объясните алгоритм на словах, буду тоже благодарен!

@Ketino · 12.10.2009, 19:43

Сообщение от Krios

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

Хотелось бы увидеть код или хотя бы фрагменты, но если объясните алгоритм на словах, буду тоже благодарен!

На словах:
Пусть есть массив М длинной D чисел.
Переменная Н будет хранить индекс первого числа искомой последовательности, К - последний индекс.
Переменная НВР и КВР - начало и конец текущей последовательности
Алгоритм:

C++

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 · 15.10.2009, 12:05 **[ТС]**

Ketino написал алгоритм поиска самой длинной неубывающей подряд идущей подпоследовательности. А требуется найти просто самую длинную неубывающую подпоследовательность. Например, для 1 0 2 1 3 2 4 3 5 это будет 1 2 3 4 5 или 0 2 3 4 5...

@Ketino · 15.10.2009, 12:13

Сообщение от Krios

Ketino написал алгоритм поиска самой длинной неубывающей подряд идущей подпоследовательности. А требуется найти просто самую длинную неубывающую подпоследовательность. Например, для 1 0 2 1 3 2 4 3 5 это будет 1 2 3 4 5 или 0 2 3 4 5...

Тогда эта задача для ветки "Алгоритмы", а не для начинающих С++

@Krios · 15.10.2009, 12:50 **[ТС]**

Сообщение от Ketino

Тогда эта задача для ветки "Алгоритмы", а не для начинающих С++

Я сомневался куда отнести эту задачу, поэтому написал в "любые вопросы", а администрация форума определила её сюда.

@Krios · 15.10.2009, 13:18 **[ТС]**

Сообщение от TanT

1. администрация форума всегда права
2. если администрация форума не права см. пункт 1. (с)

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

@Krios 0 / 0 / 0 Регистрация: 12.10.2009 Сообщений: 10
		1
	Поиск самой длинной неубывающей подпоследовательности 12.10.2009, 19:25. Показов 2132. Ответов 5 Метки нет (Все метки) Формулировка задачи: Реализовать на языке C или C++ алгоритм поиска для заданной числовой последовательности самой длинной неубывающей подпоследовательности. Хотелось бы увидеть код или хотя бы фрагменты, но если объясните алгоритм на словах, буду тоже благодарен! 0

@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... 0

@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... Тогда эта задача для ветки "Алгоритмы", а не для начинающих С++ 0

@Krios 0 / 0 / 0 Регистрация: 12.10.2009 Сообщений: 10
	15.10.2009, 12:50 [ТС]	5
	Сообщение от Ketino Тогда эта задача для ветки "Алгоритмы", а не для начинающих С++ Я сомневался куда отнести эту задачу, поэтому написал в "любые вопросы", а администрация форума определила её сюда. 0

@Krios 0 / 0 / 0 Регистрация: 12.10.2009 Сообщений: 10
	15.10.2009, 13:18 [ТС]	6
	Сообщение от TanT 1. администрация форума всегда права 2. если администрация форума не права см. пункт 1. (с) TanT, я не выражал недовольство по отношению к администрации. И уже создал эту тему в разделе "алгоритмы", так что вопрос исчерпан. 0