Решение задачи 24.
Пусть x=x1,x2, ... ,xm, y=y1,y2, ... ,yn.
Заведем матрицу A[0..m,0..n]. Элемент A[i,j] будет длиной
максимальной общей подпоследовательности y x1, ... ,xi и y y1, ..., yj. Сначала A[i,0]=A[0,j]=0, i=0, ... ,m, j=0, ... ,n.
Пусть xi=yj, тогда требуется увеличить длину максимальной общей подпоследовательности x1, ... ,xi-1 и y1, ... ,yj-1 на 1: A[i,j]=A[i-1,j-1]+1, если xi=yj.
В случае, если xi<>yj, то, очевидно,
A[i,j]=max{A[i-1,j],A[i,j-1],A[i-1,j-1]},
но так как всегда
A[i-1,j-1]<=A[i,j-1], то A[i,j]=max{A[i-1,j],A[i,j-1]}.
Величина A[m,n] и дает длину максимальной общей подпоследовательности. Найдем саму подпоследовательность. Пусть A[m,n]=d. Двигаясь по последней строке справа налево ищем самый левый элемент в этой строке со значением d. Двигаемся от него вверх по столбцу в поиске элемента столбца с минимальным первым индексом и значением d. Пусть это A[i,j]. Элемент A[i-1,j-1] обязан быть равен d-1, а xi и yi - это последние общие совпадающие элементы в x и y.
Начиная от элемента A[i-1,j-1] повторяем, как было описано выше, движение влево и вверх по матрице, находим предпоследний совпадающий элемент в x и y, и т.д.
Программа:
for i:=0 to m do A[i,0]:=0;
for j:=0 to n do A[0,j]:=0; for i:=1 to m do
for j:=1 to n do
if x[i]=y[i]
then A[i,j]:=A[i-1,j-1]+1
else A[i,j]:=max(A[i-1,j],A[i,j-1]); writeln('Длина последовательности =',A[m,n]); d:=A[m,n]; i:=m; j:=n;
while (d<>0) do begin
while A[i,j-1]=d do j:=j-1;
while A[i-1,j]=d do i:=i-1;
write('Элемент последовательности номер', d,'есть', x[i]);
i:=i-1; j:=j-1; d:=d-1; {переход к поиску предшествующего элемента в последовательности}
end;
|
