Даны две строки x и y. Строка x состоит из нулей и единиц, строка y из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 - либо в непустую последовательность букв A, либо в непустую последовательность букв B? Пусть строка 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. #include <stdio.h> #include <conio.h> #include <string.h> #define S1 "00110" #define S2 "AAAABBAA" #define N 5 #define M 8 int i, j; char ctemp; char A [N][M]; int main() { for (i=1; i<N; i++) for (j=1; j<M; j++) A[i][j] = ' '; // начальная инициализация if (S1[1] == 0) ctemp = 'A'; // 0 -> A else ctemp = S2[1]; // 1 -> A || B i=1; while ((i <= M) && (S2[i] == ctemp)) { A[1][i] = 'y'; i++; } for (i=2; i<N; i++) { j=2; while (j<M) { if (A[i-1][j-1] == 'y') { if (S1[i] == 0) ctemp = 'A'; else ctemp = S2[j]; if (S2[j] == ctemp) while ((j<=M) && (S2[j] == ctemp)) { A[i][j] = 'y'; j++; } else j++; } else j++; } } if (A[N][M] == 'y') printf ("Можно преобразовать!\n"); else printf("Нельзя преобразовать!\n"); getch(); return 0; }
|
|||||||