Решение задачи 20.
а). Пусть К(L,i) обозначает множество возрастающих подпоследовательностей длины L, которые составлены из элементов с номерами от 1 до i-1. Понятно, что их может быть очень много. Однако их число можно существенно сократить, воспользовавшись следующим фактом: из двух цепочек длины L более перспективной будет цепочка, у которой величина последнегоэлемента меньше, так как ее может продолжить большее числоэлементов. Пусть S(L,i) - это именно такая самая перспективная цепочка длины Lс минимальным по величине последним элементом, а S(i) - это множество всех цепочек S(L,i) со всевозможными L. Понятно, что в S(i) содержится не более i-1 цепочек (с длинами 1,...,i-1). Пусть мы знаем S(i).
Для того, чтобы определить, какие цепочки может продолжать i-й элемент,достаточно знать последние элементы перспективных цепочек.
Для этого удобно завести массив адресов АДР последних элементов перспективных цепочек длины 1,2,...,n. При этом легко понять, что последний элемент перспективной цепочки длины s не превышает последнего элемента перспективной цепочки длины s+1. Следовательно, для очередного i-го элемента достаточно найти только максимальную длину перспективной цепочки, для которой он будет последним. Понятно, что это будет цепочка максимальной длины, последний элемент которой меньше текущего элемента. Учитывая упорядоченность последних элементов перспективных цепочек, поиск можно сделать дихотомией. При присоединении i-го элемента к какой-нибудь цепочке длины p ее длина увеличивается на 1, a ее последним элементом становится элбмент i. При этом множество S(i+1) совпадает с S(i) за исключением одной цепочки
S(p+1,i+1) = S(p,i) сцепленная с i-ым элементом.
Для хранения цепочек удобно хранить для каждого элемента номер элемента, который ему предшествует в цепочке.
Другое решение этой задачи:
Заведем 3 массива длины N: в массиве A[1..N] помещаются самичисла последовательности. Элемент B[i] имеет значение длины максимальной возрастающей подпоследовательности, завершающейся элементом A[i], а величина C[i] есть индекс предшествующего элементу A[i] элемента вэтой максимальной последовательности (A[i]=0 есть такого элемента нет).
Если N=1, то A[1] и есть искомая подпоследовательность. При этом B[1]=1, C[1]=0. Предположим, что мы заполнили массивы A,B и C от начала до элемента M-1. Попытаемся обработать элемент A[M]. Просматривая массив A от 1 до M-1-го элемента мы ищем такое A[k], что одновременно
1) A[k]<A[M],
2) B[k] максимально.
Очевидно, что для того, чтобы получить максимальную по длине подпоследовательность, заканчивающуюся A[M], этот элемент надо приписать к подпоследовательности с последним элементом A[K]. Получаем, что B[M]=B[K]+1, C[M]=K.
Пусть мы обработали все N элементов массива A. Находим максимальный элемент массива B, пусть это будет B[K]. По построению это длина максимальной подпоследовательности.
Выписываем эту подпоследовательность: полагаем j:=k; печатаем элемент A[j]; так как предшествующий в последовательности элемент имеет индекс C[j], то делаем присваивание j:=C[j], распечатываем этот элемент и т.д., до тех пор, пока j не станет 0 (т.е. мы дошли до начала последовательности).
Запись алгоритма:
for i:=2 to N do B[i]:=0;
C[1]:=0; B[1]:=1; Max:=1; IndexMax:=1;
for i:=2 to N do
for j:=1 to i-1 do
if (A[j]<A[i]) AND (B[i]<B[j]+1)
then begin
C[i]:=j;
B[i]:=B[j]+1;
if B[i]>Max
then begin Max:=B[i]
IndexMax:=i
end;
while IndexMax<>0 do begin
writeln(A[Index-Max]);
IndexMax:=C[IndexMax]
end;
В программе в переменной Max хранится максимальная найденная до сих пор длина подпоследовательности, в IndexMax находится индекс последнего элемента этой подпоследовательности.
Структура данных, каждый элемент которой (в данном случае A[i]) содержит ссылку (в этой задаче C[i]) на предыдущий элемент (или, если требуется, на последующий элемент) называется однонаправленным списком. Если у элемента есть ссылка как на предыдущий, так и на последующий за ним элемент, то список двунаправленный (его можно реализовать, используя не один массив для индексов, а два).
б). Частный случай пункта в).
в). Заведем матрицу С[0..m+1,1..n]. В ней i-тая строка будет хранить информацию о последовательностях с i-1 разрывами; j-ый элемент в этой строке есть длина самой длинной подпоследовательности элементов "хвоста" массива А ( от j-го элемента до n-го), начинающейся в j-ой позиции и с не более чем i-1 разрывом.
Правило заполнения матрицы:
Заполним нулевую строку нулями (чтобы можно было заполнить первую строку по общему алгоритму).
Для каждого номера строки i от 1 до m+1 выполнить следующие действия:
Для j-го элемента массива A (j изменяется от n до 1) находим максимальную по длине подпоследовательность, которую можно присоединить к этому элементу так, чтобы получить подпоследовательность максимальной длины с не более чем i-1 разрывом. Для этого мы:
1) ищем элемент A[k] последовательности A, больший A[j], стоящий в массиве A правее j-го элемента и с максимальным С[i,k];
2) затем просматриваем элементы i-1 -ой строки матрицы С, начиная с j+1 -го и до конца, и находим C[i-1,s] - максимальный из них;
3) сравниваем C[i-1,s] с С[i,k]. Больший из них (обозначим его C[row,col]), увеличенный на 1, запоминаем в C[i,j]. Это и будет длина максимальной подпоследовательности, начинающейся в позиции j, с не более чем i-1 разрывом.
4) Запоминаем индексы row и col элемента массива C, предшествующего C[i,j], в ячейках X[i,j] и Y[i,j] соответственно.
После окончания цикла максимальный элемент m+1 -ой строки матрицы C и есть максимальная длина возрастающей подпоследовательности с m разрывами. Выписать всю подпоследовательность можно следующим образом: для каждого элемента подпоследовательности в массивах X и Y хранится информация о предшественнике. Мы, начиная с максимального элемента m+1 -ой строки матрицы C, восстанавливаем всю подпоследовательность.
Обоснование алгоритма:
Пусть мы знаем C[i-1,j] для всех j от 1 до n и для некоторого i, а также C[i,k] для k от j+1 до n. Мы хотим вычислить C[i,j].
Для j-го элемента массива А существует максимальная по длине подпоследовательность с не более чем i-1 -им разрывом, начинающаяся с A[j]. Второй элемент (обозначим его A[k]) этой максимальной подпоследовательности (если он, конечно, есть) может быть
1) больше, чем A[j]. Тогда мы находим его среди элементов, обладающих следующими свойствами:
а) k>j,
б) C[i,k] максимальный (т.е. мы присоединяем к A[j] максимальную по длине подпоследовательность с не более чем i-1 разрывом, формируя подпоследовательность опять не более чем с i-1 разрывом);
2) меньше или равный, чем A[j]. Тогда мы ищем его среди элементов, обладающих следующими свойствами:
а) k>j;
б) C[i-1,k] максимальный (т.е. мы присоединяем максимальную подпоследовательность с не более чем i-2 -мя разрывами, формируя подпоследовательность с не более чем i-1 разрывом).
Полученная подпоследовательность получается максимальной длины, так как длина подпоследовательности, начиная с A[k], максимальная.
Упоминавшиеся выше индексы row и col, которые запоминаются в X[i,j] и Y[i,j] соответственно, обозначают
col - индекс следующего за A[j] элемента в максимальной по длине подпоследовательности, начинающейся в позиции j и имеющей не более i-1 разрыва;
row-1 - максимальное количество разрывов в подпоследовательности, начинающейся в A[col].
{Программа написана Д.Медведевым и А.Гавриловым}
const max=100; {максимальная длина массива A}
var
sw,l,i,j,k,n,m,maxind,swind:integer;
c:array [0..max,1..max] of integer;
x,y:array [1..max,1..max] of integer;
a,b:array [1..max] of integer;
begin
Write('Введите N:');
readln(n);
Writeln('Введите последовательность');
for i:=1 to n do
read(a[i]);
readln;
Write('Введите количество разрывов подпоследовательности:');
readln(m);
fillchar(c,sizeof(c),0); {зануление с, x и y} fillchar(x,sizeof(x),0);
fillchar(y,sizeof(y),0);
for i:=1 to m+1 do
for j:=n downto 1 do
begin
c[i,j]:=1;
for k:=j+1 to n do
if (a[k]>a[j]) and (c[i,k]>=c[i,j]) then
begin
c[i,j]:=c[i,k]+1;
x[i,j]:=k;
y[i,j]:=i;
end;
for k:=j+1 to n do
if c[i-1,k]>=c[i,j] then
begin
c[i,j]:=c[i-1,k]+1;
x[i,j]:=k;
y[i,j]:=i-1;
end;
end;
maxind:=1;
for i:=1 to n do
if c[m+1,i]>c[m+1,maxind] then
maxind:=i;
l:=c[m+1,maxind];
j:=maxind;i:=m+1;k:=1;
while (c[i,j]<>1) do
begin
b[k]:=j; {в массив b выписываем индексы элементов} inc(k); {максимальной по длине подпоследователь}
sw:=x[i,j]; {ности в прямом порядке}
i:=y[i,j];
j:=sw;
end;
b[k]:=j;
for i:=1 to k do write(a[b[i]],' ');
writeln;
writeln('Длина=',l);
end.
|
