94
правки
Изменения
Нет описания правки
*""(пустая строка) есть правильная скобочная последовательность;*правильная скобочная последовательность, взятая в скобки есть правильная скобочная последовательность;(*)*скобочная последовательность, к которой приписана слева или справа другая скобочная последовательность, есть правильная скобочная последовательность;}}''Примеры правильных скобочный последовательностей''*$((()()()()))$*$(())(()())$
Пусть нам дана скобочная последовательность записанная в строку s. Возьмем переменную a, a = 0. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем a на 1, закрывающую - уменьшаем на 1. Если на протяжении всего перебора a было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
''псевдокод'':
function check(s: string): boolean;
Надо отметить что, скобочные последовательности могут состоять не только из одного типа скобок, при этом недопустимо такое расположение, когда один тип скобок закрывает другой:
*$()[()]\{()()[]\} $ - верно *$[(]\{\}) $ - неверно
В этом случае для проверки надо будет использовать стек.
== Лексикографический порядок порядок правильных скобочных последовательностей==
Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей будем интерпретировать открывающуюся скобку как "0", а закрывающуюся как "1"(**). Тогда первая последовательность с n открывающимися скобками будет иметь вид:
{| border="1" cellpadding="3" | (||(||(||(||...||(||(||(||)||)||)||...||)||)||)||) ||(***) |-0000 |0||0||0||0||...000111||0||0||0||1||1||1||...1111||1||1||1||1 |}
что соответствует самому маленькому возможному числу, а последняя:
{| border="1" cellpadding="3" | (||)||(||)||...||(||)||(||)||(||)||...||(||)||(||) |-0101 |0||1||0||1||...010101||0||1||0||1||0||1||...0101||0||1||0||1 |}
что соответствует самому большому возможному числу.
Для последовательностей с разным типом скобок надо определять свой порядок, например "("<"["<")"<"]".
''Примеры лексикографического порядка для n и k, где n - число открывающихся скобок, а k - число видов скобок:''
{| border="1" cellpadding="3" |n = 3;||k = 1 |- |$((()))$||$(()())$||$(())()$||$()(())$||$()()()$ |}
Алгоритм генерации лексикографического порядка будет предложен ниже.
== Количество правильных скобочных последовательностей. Числа Каталана==
Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.
{{Определение|id = def1|definition =Числа Каталана представляют собой:{{---}} последовательность чисел, выражающихЖ - *количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями; - *Количество способов соединения 2n точек на окружности n непересекающимися хордами; - *количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями; - *Количество правильных скобочных последовательностей имеющих n открывающихся скобок.}}
Числа Каталана удовлетворяют следующему рекурентному соотношению:
$c_0 $ = 1; - так как существует только одна скобочная последовательность с 0 открывающихся скобок - пустая
$C_n $ = (Сумма по i от 1 до n - 1) C_i * C_(n - 1 - i).
Это соотношение легко получается из (*). Для этого надо перебрать все возможные последовательности d_1 и d_2, являющиеся правильными скобочными последовательностями, такие, что (d_1)d_2 образуют новые правильные скобочные последовательности необходимой нам длины.
