Показать сообщение отдельно
Старый 20.12.2013, 10:58   #5 (permalink)
Vladimir_S
Специалист
 
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 27,807
Сказал(а) спасибо: 340
Поблагодарили 583 раз(а) в 208 сообщениях
Репутация: 113184
По умолчанию

Ну вот, извольте. Итак, имеется неупорядоченный массив a в диапазоне 1..n. Задача: найти наибольший по длине фрагмент массива, в котором элементы упорядочены по возрастанию.
Приняты следующие обозначения:
i - переменная (счетчик) цикла.
mx - текущее значение максимальной длины упорядоченного фрагмента. Исходное значение mx=0.
k - текущее значение длины упорядоченного фрагмента.
j - счетчик элементов упорядоченного фрагмента.
imx - порядковый номер первого элемента упорядоченного фрагмента. Исходное значение imx=0.

Код:
{Задаём исходные значения:}
i:=2;
mx:=0;
imx:=0;
{Организуем цикл по всему исходному массиву:}
while i<=n do
 {Проверяем условие "если последующий элемент больше предыдущего":}
 if a[i]>a[i-1] then
 {Если указанное условие выполнено, то:}
  begin
  {Задаем исходные значения k и j. Далее "движемся" по массиву, используя счетчик j. Значение i остаётся соответствующим второму элементу упорядоченного фрагмента:}
   j:=i;
   k:=1;
   {Наращивая j, движемся по массиву до тех пор, пока или массив не кончится, или условие упорядоченности (текущий элемент больше предыдущего) не нарушится. В результате определяем длину (k) упорядоченного фрагмента:}
   while (j<=n) and (a[j]>a[j-1]) do
    begin
     j:=j+1;
     k:=k+1;
    end;
    {Проверяем, не превышает ли полученная длина k значение максимальной протяженности упорядоченного фрагмента, полученное после обработки предыдущей части исходного массива, и если превышает, то переопределяем как саму длину (mx), так и номер первого элемента упорядоченного фрагмента (imx):}
    if k>mx then
     begin
      mx:=k;
      imx:=i-1;
     end;
    {Смещаем глобальную нумерацию (i) на длину найденного упорядоченного фрагмента с тем, чтобы продолжить глобальный цикл:}
    i:=i+k;
  end
  {Если указанное в начале условие соотношения пары соседних элементов не выполнено (последующий меньше или равен предыдущему), то продолжаем движение вдоль исходного массива:}
  else i:=i+1;
{Выводим полученный результат (длину наибольшего упорядоченного фрагмента и сам фрагмент):}
writeln('Максимальная последовательность возрастания=',mx);
for i:=imx to imx+mx-1 do
  write(a[i],' ');
{Останавливаем, а потом завершаем программу:}
readln
end.
Vladimir_S вне форума   Ответить с цитированием
Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070