Re: Неубывающая подпоследовательность

From

Viktor Karev ()

To

All ()

Date

2000-02-22T21:20:08Z

Area

RU.ALGORITHMS

From: "Viktor Karev" <karev@post.krascience.rssi.ru>

Приветствия, Dmitry Buzin!

>     Требуется найти самую длинную неубывающую подпоследовательность в
> последовательности целых чисел, избежав при этом полного перебора.
>     Задача, в принципе, не очень сложная, но ничего, кроме модификации
метода
> бинарного поиска в голову не приходит. ;)

Эта задача очень хорошо описана у Д.Гриса в книге "Наука программирования".
Основная идея: если есть последовательность b[0:i-1]. Ясно, что для каждого
k есть минимальное значение m, завершающее в этой последовательности
восходящую подпоследовательность длины k.
Теперь добавим еще один член последовательности, b[i].
Если b[i]>=m, то просто увеличиваем k, и новое m равно b[i].
Если же b[i]<m, то выясняется, что нам нужен массив m[], в котором мы
запоминаем значения m для каждого k.

Введем обозначение lup(s) - длина самой длинной восходящей
последовательности из s.
Таким образом, программа имеет пред- и постусловие
Q: n>0
R: k=lup(b[0:n-1])

.... Анализ пропущен.

Вводится инвариант цикла
P: ((0<=i<=n) and (k=lup(b[0:n-1])) and
    (для любого j: 1<=j<=k, справедливо, что m[j] является наименьшим
значением, завершающим восходящую последовательность длины k в b[0:i-1])

i:=1; k:=1; m[1]:=b[0]; {P}
пока i<>n цикл
  если b[i]<=m[k]      то k:=k+1; m[k]:=b[i];
       b[i]<m[1]       то m[1]:=b[i];
       m[1]<=b[i]<m[k] то
           ** Установить m[j-1]<=b[i]<m[j]:
           h:=1; j:=k;
           {Инвариант: (1<=h<j<=k) and (m[h]<=b[i]<m[j])}
           пока h<>j-1 цикл
             e:=(h+j)%2;
             если m[e]<=b[i] то h:=e
                  m[e]>b[i]  то j:=e
             конец если
           конец цикла
           m[j]:=b[i]
  конец если
  i:=i+1
конец цикла

Виктор
--- ifmail v.2.15dev4
 * Origin: Персональный компьютер (2:5020/400)