Задача 22.
Если мы из корректно записанного арифметического выражения, содержащего числа, знаки операций и открывающие и закрывающие круглые скобки выбросим числа и знаки операций, а затем запишем оставшиеся в выражении скобки без пробелов между ними, то полученный результат назовем правильным скобочным выражением [скобочное выражение "(()(()))" - правильное, а "()(" и "())(" - нет].
Найти число правильных скобочных выражений, содержащих N открывающихся и N закрывающихся скобок. N вводится с клавиатуры. N неотрицательное целое число.
|
Решение задачи 22.
Назовем скобочное выражение элементарным, если оно представимо в виде (S), где S - правильное скобочное выражение. Очевидно, что каждое непустое скобочное выражение можно единственным образом представить в виде
ES,
где
E - элементарное скобочное выражение;
S - скобочное выражение (возможно, пустое).
Обозначим через S(n) число правильных скобочных выражений с 2n скобками. Тогда число элементарных скобочных выражений с 2n
скобками есть S(n-1). Таким образом
S(n)=(S(i-1)*S(n-i)).
Замечая, что S(0)=1, - одно пустое скобочное выражение,
мы приходим к алгоритму сложности O(n2).
ДРУГОЕ РЕШЕНИЕ этой задачи:
Будем изображать знаком / открывающую скобку, а \ - закрывающую. Правильное скобочное выражение (ПСВ) при n=1 будет выглядеть
так:
Если мы возьмем картинку
то все ПСВ с n=2 будут такими:
- то есть каждому ПСВ соответствует свой единственный и неповторимый путь между вершинами 0 и 2. Аналогично, все ПСВ с n=3 будут описываться путями в графе
и т.д. Подсчитаем число ПСВ (число путей) при n=3.
В вершину A мы можем попасть единственным способом - из точки 0, равно в B,C и точку 1 можно попасть, соответственно, только из точек A, B, A. В E можно попасть как из 1, так и из B, поэтому пометка E есть сумма пометок этих узлов, т.е. 2. В D можно попасть либо из Cи (пометка 1), либо из E (пометка 2), и, следовательно, пометка D=3 и т.д.
Аналогично находим количество ПСВ для любого n.
|
