Задача 18.
Даны две строки x и y. Строка x состоит из нулей и единиц, строка y из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 - либо в непустую последовательность букв A, либо в непустую последовательность букв B?
|
Решение задачи 18.
Пусть строка S1 состоит из цифр 0 и 1 и имеет длину N, а строка S2 (из символов A и B) - длину M.
Заведем матрицу А размера N на M, при этом строки матрицы помечаются i-ой цифрой строки S1, а j-й столбец - j-м символом строки S2.
Возьмем в качестве примера S1='00110', S2='AAAABBAA'.
Первая цифра строки S1 (цифра 0) может быть преобразована в одну из последовательностей букв 'A','AA','AAA','AAAA', являющиеся префиксами строки S2. Заносим символ 'x' в те столбцы первой строки, буквы-пометки которых соответствуют последним буквам возможных последовательностей. Таким образом, помечаются элементы A[1,1], A[1,2], A[1,3] и A[1,4].
Шаг алгоритма: будем преобразовывать очередную цифру S1[i], которой соответствует строка i.
Находим 'x' в предыдущей строке при просмотре ее слева направо (этому столбцу соответствует последняя буква в какой-то из непустых последовательностей букв, порожденных на предыдущем шаге). Если текущую цифру можно преобразовать в последовательность букв, помечающих следующие за данным столбцы, то в этих столбцах в данной строке ставим 'x'.
Далее от места над последней помеченной ячейкой ищем в предыдущей строке 'x' и, когда находим, повторяем указанные выше операции.
Эти действия проводим далее для i=2,...,N.
Вид матрицы после N шагов:
Замечание: Можно обойтись и одномерным массивом. В самом деле, при заполнении следующей строки мы обращаемся только к элементам предыдущей строки, к каждому - по одному разу.
Алгоритм (без учета замечания) может быть следующим:
for i:=1 to N do
for j:=1 to M do
A[i,j]:=' '; {инициализация}
if S1[1]=0
then element:='A' {0 преобразуется в A}
else element:=S2[1]; {1 - в A или в B}
i:=1;
while (i<=M) and (S2[i]=element) do begin {первый шаг}
A[1,i]:='x';
i:=i+1
end;
for i:=2 to N do begin
j:=2;
while j<M do begin {просмотр строки i}
if A[i-1,j-1]='x'
then begin
if S1[i]=0
then element:='A'
else element:=S2[j];
if S2[j]=element
then
while (j<=M) and (S2[j]=element) do begin
A[i,j]:='x';
j:=j+1;
end {end for while}
else j:=j+1
end {end for then}
else j:=j+1
end {end for while}
end; {end for for}
if A[N,M]='x'
then writeln('Можно преобразовать') else writeln('Нельзя преобразовать');
Напишите программу, использующую одномерный массив.
|
