Задача 1
Вводится последовательность, состоящая из N пар символов (ai,bi). Каждая пара определяет порядок предшествования символов, например, пара (b,с) означает, что символ "b" предшествует символу "с". Из порядка (b,с) и (с,a) следует порядок (b,a). Необходимо определить, является ли введенная последовательность:
а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку (A1,A2,...,As) в порядке предшествования;
б) противоречивой, т.е. для некоторых символов x,y можно
получить одновременно порядок как (x,y) так и (y,x);
|
Решение задачи 1.
Пусть при записи этих N пар встретилось всего K различных символов, которые образуют множество X.
Идея решения задачи состоит в последовательном присвоении каждому символу s из Х номера, который определяет количество Р(s) элементов, предшествующих ему, с учетом свойства транзитивности (из (с,b) и (b,а) следует (с,а)). Это осуществляется следующим образом:
Первоначально предполагается, что каждому символу не предшествует ни один символ, т.е. Р(s)=0 для любого s.
При просмотре очередной пары (x,y) символу y присваивается большее из значений P(x)+1, P(y).
Очевидно, что при первом просмотре всех пар из входной последовательности определятся все упорядоченные цепочки длины 2, т.е. состоящие из 2 элементов. Поэтому номера некоторых элементов будут как минимум 1. При каждом из следующих просмотров входной строкивозможно несколько вариантов.
Не произошло изменения ни одного из номеров символов. Если при этом номера символов различны и лежат в пределах от 0 до N-1, то эта нумерация определяет полный порядок. Иначе порядок неполный.
Номер некоторого символа превысил N-1. Это произошло потому, что рост номеров неограничен, т.е. осуществляется циклически. Следовательно порядок противоречив.
Легко понять, что число просмотров не превысит N.
Вариант 2. Рассмотрим следующий метод:
Заведем массивы
A: array [1..N,0..N] of byte
и
Cnt: array[1..N] of byte;
сначала A[i,0]=0 и Cnt[i]=0 для любого i.
Пусть среди 2*N символов, образующих N пар, есть ровно K различных. Перенумеруем их от 1 до K. Будем считать, что пары составлены не из символов, а из соответствующих им номеров.
В i-ю строчку матрицы A будем заносить те элементы, которые являются вторыми элементами в парах с первым элементом i. В A[i,0] будет храниться текущее число этих элементов. Обработка пары (i,j) будет выглядеть следующим образом:
A[i,0]:=A[i,0]+1; {количество увеличилось на 1}
A[i,A[i,0]]:=j; {вставляем j на первое свободное место}
В Сnt[i] будет храниться число пар, у которых элемент i является вторым в паре.
Если все символы без повторений, использованные для записи пар, можно выписать в цепочку в порядке предшествования, то у этой цепочки должен быть первый символ s, у которого нет предшествующего и которому соответствует Cnt[s]=0.
Может быть несколько ситуаций:
1. Такой элемент единственный - следовательно, это начало цепочки. Отбрасываем s из цепочки и убираем все пары с первым элементом s из множества пар, корректируя при этом массив Cnt:
for i:=1 to A[0,s] do
Сnt[A[s,i]]:=Cnt[A[s,i]]-1;
после чего опять ищем элемент s, у которого нет предшествующего и которому соответствует Cnt[s]=0.
2. Таких элементов несколько, следовательно, между ними нельзя определить порядок предшествования - система неполна.
3. Таких элементов нет - следовательно, система противоречива.
|
