94
правки
Изменения
Нет описания правки
<wikitex>
== Определения ==
{{Определение
|id = def1
|definition ='''Скобочная последовательность''' {{---}} класс комбинаторных объектов, представляющий собой последовательность скобочных символов.}}
''Примеры скобочных последовательностей:''
*$(())))($
*$)()()))()(()())$
*скобочная последовательность, к которой приписана слева или справа другая скобочная последовательность, есть правильная скобочная последовательность;
}}
''Примеры правильных скобочный последовательностей:''
*$((()()()()))$
*$(())(()())$
== Алгоритм проверки правильности скобочной последовательности ==
Пусть нам дана скобочная последовательность записанная в строку $s$. Возьмем переменную $a$, $a = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $a $ на $1$, закрывающую - уменьшаем на $1$. Если на протяжении всего перебора $a $ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
''псевдокод'':
Надо отметить что, скобочные последовательности могут состоять не только из одного типа скобок, при этом недопустимо такое расположение, когда один тип скобок закрывает другой:
''Примеры скобочных последовательностей с несколькими типами скобок:''
*$( ) [ ( ) ]\{()()[]\}$ - верно
*$[(]\{\})$ - неверно
что соответствует самому большому возможному числу.
Для последовательностей с разным типом скобок надо определять свой порядок, например "("<"["<")"<"]".
''Примеры лексикографического порядка для $n $ и $k$, где $n $ - число открывающихся скобок, а $k $ - число видов скобок''
{| border="1" cellpadding="3"
|$n = 3$||$k = 1$
|-
|$((()))$||$(()())$||$(())()$||$()(())$||$()()()$
{| border="1" cellpadding="3"
|$n = 2$||$k = 2$
|-
|$()[]$||$([])$||$[()]$||$[]()$
Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.
{{Определение
|id = def1
|definition =Числа Каталана {{---}} последовательность чисел, выражающихЖвыражающих:
*количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями;
*Количество количество способов соединения 2n точек на окружности n непересекающимися хордами;
*количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями;
*Количество количество правильных скобочных последовательностей имеющих n открывающихся скобок.}}Числа Каталана удовлетворяют следующему рекурентному соотношению:
Это соотношение легко получается из (*). Для этого надо перебрать все возможные последовательности $c_0d_1$ = 1; - так как существует только одна скобочная последовательность с 0 открывающихся скобок - пустаяи $d_2$, являющиеся правильными скобочными последовательностями, такие, что $(d_1)d_2$ образуют новые правильные скобочные последовательности необходимой нам длины.
''Генерация следующей скобочной последовательности:''
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то - "No solution". Воспользуемся интерпретацией (**). Чтобы получить следующий битовый вектор надо найти самый последний нулевой элеменьэлемент, заменить его на единицу, а элементы следующие за ним сделать минимально возможными(все нули). Тоже самое и со скобочными последовательностями, только после замены нуля на единицу оставшиеся скобки надо расположить в минимальном порядке (в виде (***)):
function next(var s: string): boolean;
end;
Если эта функция после выполнения выводит $true $ тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution".
''Получение лексикографического порядка:''
Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n $ открывающимися скобками:
procedure (n: integer);
end;
Так же с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших $n$.
