数列与规律.docx

探索规律的奥秘——括号序列摘要本文探讨了在一定限制条件下“合法括号序列”的数量。使用几种不同的方法，先有条理地分析、探索出递推的规律，进而推导得出公式。引入 定义“括号序列”为一串由“(”和“)”组成的序列。定义“合法的括号序列”为一个可以将“(”和“)”配对，从而满足以下条件的括号序列：“(”和“)”数量相等。两对括号之间要么是包含关系（形如“(())”），要么互不相交（形如“()()”）.不难证明，一个合法的括号序列只有一种合法的配对方法。接着，我们把一个括号序列写成“分行”形式：例如把()(()((())()))(())写成：()()() ()( )()( )() ()则我们定义“合法括号序列的深度”为其“分行”形式所占用的行数（例如以上序列的“深度”就是4）。当然，也有更严谨的定义方法：“深度”就是原序列任意前缀中“(”和“)”数量之差的最大值。也就是说，设原序列为A，从A的开头开始从左往右选取连续的一些字符，就能“截”出一串新的括号序列V（不一定合法），并求得V序列中“(”与“)”数量之差。通过这种方式所能得到的最大的差，就是A序列的深度。为什么？因为在“分行形式”中，从开头往右看，看到一个“(”就代表着“以后的字符向下进一行”，看到“)”就代表着“以后的字符向上回退一行”，两者相抵，所以把两者数量相减，就能得到V序列最后一个括号的深度。这样的话，最深的括号的深度——也就是所得差的最大值——即为A序列的深度，也就是其分行形式占用的行数。因此，以上两种对“深度”的定义等价。问题来了：给定正整数N和K，找出一种高效的算法，用以求包含N对括号且深度为K的合法括号序列数量。一种简单但是错误的算法显而易见，解决此问题的高效方法是递推。但是，每次从哪几个数递推到那几个数？递推几次？按照什么规律递推？不难想到的一种方法是：首先，死算出N=1情况下的结果：当K=1，所求结果为1。对应的序列有：()当K≠1，所求结果为0。于是，把N=1时的所有序列：()在任意合法位置添加一对括号：()() (()) 新添加的用红色标记。 就不重不漏地得到了N=2时的所有序列。故当N=2时：当K=1时，所求结果为1。对应的序列有：()()当K=2时，所求结果为1。对应的序列有：(())当K≠1且K≠2时，所求结果为0。于是，把N=2时的所有序列： ()() (())在任意合法位置添加一对括号：()()() ((()))(())()()(())()(())(()())(()())(())() 就不重不漏地得到了N=3时的所有序列？这下，我们发现了问题！图中标出的三对序列被重复计算了！所以，以上算法——虽然它可以通过改进来变得很高效——归根结底是错误的！让我们总结一下错因：在以上方法中，我们是如何得到某一个序列的？从最基本的“()”开始，我们不断在任意合法位置添加一对括号，最后得到所有序列。但是，以这种方式，我们可以用多种顺序添加括号，来得到同一个序列，因而导致重复计算。也就是说，导致错误的是，一个序列，有多种得到它的方法！所以，我们要适当调整添加括号的顺序，使得每一个序列有且仅有一种得到它的方法——至少在“不断添加括号”的思路下是如此。一种正确但略显复杂的算法如何调整顺序呢？不难想到，可以“从左往右”添加括号。位于同一个合法括号序列中的两对括号A和B，如果A的左括号在B的左括号左边，就说A在B左边；反之，就说A在B右边。举个例子：对括号序列()(()((())()))(())，在“从左往右添加”的方法下，是这样得到它的：（新添加的用红色标出。)1、()2、 ()() 3、 ()(()) 4、 ()(()()) 5、 ()(()(())) 6、 ()(()((()))) 7、 ()(()((())()))()(()((())()))()()(()((())()))(())这时，我们发现，在添加的过程中，出现了两种现象。第一，每次，把当前序列中红色左括号右边（不包括它自己）的部分截取出来，那么其中一定全是“)”；第二，每次红色的一对括号的左右两半都是紧挨着的。为什么？道理并不难。第一：因为我们“从左往右”添加括号，所以每次添加的一对括号一定是“最右边”的一对。又因为我们用左括号位置来判别两对括号之间的“左右”关系，所以新添加的左括号一定是最右边的左括号，进而，它的右边没有左括号，就全是右括号。第二：因为红色左括号的右边全是右括号，所以如果红色右括号不是紧挨其右，红色的一对括号之间就有且仅有一些黑色右括号。这样当前序列就不合法了，因