Написать программу на C

[Vladis1av]

Даны 2 последовательности "x" и "y". Найти последовательность "z", которую можно получить вычеркиванием элементов как из "x", так и из "y"

[Stilet]

Наработки есть?

[Vladis1av]

в данный момент нет

[Vladis1av]

нашел эту программу на паскале:
Пусть 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;