Решение задачи 25.
В последовательностях x и y избавляемся от лидирующих нулей. Если хоть одна из последовательностей стала пустой, то z=0. Иначе крайние левые цифры и в x и в y есть 1.
Запускаем на полученных последовательностях алгоритм задачи 24 (для получения максимального z необходимо, чтобы старшая цифра z была 1 и двоичная запись z имела максимальную длину), но при этом для каждого A[i,j] - длины последовательности, необходимо хранить добавочно и саму последовательность; при присвоении значения A[i,j] одновременно будем запоминать и последовательность максимальной длины. Если таких несколько, то берем из них последовательность с максимальным значением. Поэтому алгоритм задачи 23 запишется так:
Пусть S[0..m,0..n] - массив строк. В S[i,j] будет храниться подпоследовательность, длина которой A[i,j].
for i:=0 to m do A[i,0]:=0;
for j:=0 to n do A[j,0]:=0;
for i:=0 to m do
for j:=0 to n do S[i,j]:='';
for i:=1 to m do
for j:=1 to n do begin
if x[i]=y[j]
then begin
A[i,j]:=A[i-1,j-1]+1; S[i,j]:=S[i-1,j-1]+x[i];
end;
A[i,j]:=max(A[i,j],A[i-1,j],A[i,j-1]); S[i,j]:=max(S[i,j],S[i-1,j],S[i,j-1]);
end;
write(A[m,n],'- длина',S[m,n]);
Попробуйте не заводить массив S[0..m,0..n], а обойтись одномерным массивом S[0..n].
|
