【输出样例】
5
算法分析
第一种解法——回溯法
设 total 为输出序列的总数目；输出序列的尾指针为 l，堆栈的栈首指针为 tp，当前准
备入栈的操作数为 r。我们采用回溯法计算输出序列的总数目。
状态（tp，l，r）：栈首指针，输出序列指针，当前准备入栈的操作数；
边 界 条 件 和 目标 （ r=n+1 ） ： 所 有 操 作 数 入 栈 ， 即 得 到 一 个 输 出 序 列 。 此 时 ，
total+1，回溯；
搜索范围：有两种操作
栈非空（tp<>0），则栈顶元素进入输出序列，递归子状态（ tp-1，l+1，r）；
操作数序列的首元素入栈， 递归子状态（tp+1，l，r+1）。
由此得出递归程序
procedure search（tp，l，r）;
begin
if r=n+1{若得到一个输出序列，则输出序列的总数目+1，回溯}
then begin total:= total+1;exit{回溯} end;{then}
if tp<>0{若栈非空，则栈顶元素进入输出序列，递归}
then search（tp-1，l+1，r）;
search(tp+1，l，r+1); {操作数序列的首元素入栈， 递归}
end;{ search }
主程序调用 search（0，0，1）后得出的 total 即为输出序列的总数目。该算法的时间复
杂度为 O(2
n
)。
第二种解法——计算 Catalan 数
上述方法毕竟是一种代价比较高的搜索方法。能否找到出入栈的数学规律，建立一种
正确和简便的解析办法呢，能够。
对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘ 1’，出栈设为状
态‘0’。n 个数的所有状态对应 n 个 1 和 n 个 0 组成的 2n 位二进制数。由于等待入栈的操作
数按照 1‥n 的顺序排列、入栈的操作数 b 大于等于出栈的操作数 a(a≤b)，因此输出序列的
总数目=由左而右扫描由 n 个 1 和 n 个 0 组成的 2n 位二进制数，1 的累计数不小于 0 的累计
数的方案种数。
在 2n 位二进制数中填入 n 个 1 的方案数为 ，不填 1 的其余 n 位自动填 0。从
中减去不符合要求（由左而右扫描，0 的累计数大于 1 的累计数）的方案数即为所求。
不符合要求的数的特征是由左而右扫描时，必然在某一奇数位 2m+1 位上首先出现
m+1 个 0 的累计数和 m 个 1 的累计数，此后的 2（n-m）-1 位上有 n-m 个 1 和 n-m-1 个 0。
如若把后面这 2（n-m）-1 位上的 0 和 1 互换，使之成为 n-m 个 0 和 n-m-1 个 1，结果得 1 个
由 n+1 个 0 和 n-1 个 1 组成的 2n 位数，即一个不合要求的数对应于一个由 n+1 个 0 和 n-1 个
1 组成的排列。反过来，任何一个由 n+1 个 0 和 n-1 个 1 组成的 2n 位二进制数，由于 0 的个
数多 2 个，2n 为偶数，故必在某一个奇数位上出现 0 的累计数超过 1 的累计数。同样在后
面部分 0 和 1 互换，使之成为由 n 个 0 和 n 个 1 组成的 2n 位数，即 n+1 个 0 和 n-1 个 1 组成
