n&个元素顺序入栈，则可能的出栈序列有多少种？&转&
有关堆栈和Catalan数的思考
形如这样的直角三角形网格，从左上角开始，只能向右走和向下走，问总共有多少种走法？
问题的由来：编号为 1 到 n 的 n 个元素，顺序的进入一个栈，则可能的出栈序列有多少种？
对问题的转化与思考：n 个元素进栈和出栈，总共要经历 n 次进栈和 n 次出栈。这就相当于对这 2n 步操作进行排列。
一 个模型：一个 n*n
的正方形网格，从左上角顶点到右下角顶点，只能向右走和向下走。问共有多少种走法。如果将向右走对应上述问题的进栈，向下走对应上述问题的出栈，那么，可
以视此模型为对上述问题的具体描述。而解决此问题，只要在总共从左上角到右下角的2n步中，选定向右走的步数，即共有C(n
2n)中走法。
但是存在一个问题，如果走法越过了对角线，那么对应到上述问题是出栈数比入栈数多，这是不符合实际的。
对以上模型进行处理，对角线将以上正方形网格分成两部分，只留下包含对角线在内的下半部分，那么就不会出现越过对角线的问题。而这问题就是开始提出的问题。
-------------------------------------------------------
问题等价于：n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？
解答： 设P2n为这样所得的数的个数。在2n位上填入n个1的方案数为 C（n 2n）
不填1的其余n位自动填以数0。从C（n 2n）中减去不符合要求的方案数即为所求。
不合要求的数指的是从左而右扫描，出现0的累计数超过1的累计数的数。
不合要求的数的特征是从左而右扫描时，必然在某一奇数2m+1位上首先出现m+1个的累计数，和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组成的2n位数，必对应于一个不合要求的数。
用上述方法建立了由n＋1个0和n－1个1组成的2n位数，与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应。
是由4个0和4个1组成的8位2进制数。但从左而右扫描在第5位（显示为红色）出现0的累计数3超过1的累计数2，它对应于由3个1，5个0组成的。
因而不合要求的2n位数与n＋1个0，n－1个1组成的排列一一对应，故有
P2n ＝ C（n 2n）— C（n＋1 2n）
这个结果是一个“卡塔兰数”Catalan，在组合数学中有介绍，可以参阅有关资料。
-----------------------------------------------------
是否可以用一种更合乎思维习惯的方式解决这个问题呢
可以把这个问题描述为一个二元组，(n, 0) 表示有n个元素等待进栈, 0 个元素已进栈, 这相当于问题最初的状况.
接着问题转化为(n-1,1). 可以这么说(n,0) = (n-1,1).
而对于(n-1,1)则相当于(n-1,0)+(n-2,2).
(n-1,0)表示栈中的一个元素出栈, (n-2, 2)表示又有一个元素入栈.
把问题一般话,则(n,m)的排列问题可以转化为(n,m-1)+(n-1,m+1) 此时m&=1,
因为必须栈中有元素才可以出栈.当m=0则(n,0)的问题只能转化为(n-1,1). 当问题为(0,
m)时得到递归边界,这个问题的解是只有一种排列.
#include &stdio.h&
#define ELEMNUM 6;
int getPermuStack(int n, int m)
if(n == 0)//递归边界
if(m == 0)//(n,0)问题的处理
return getPermuStack(n-1, 1);
return getPermuStack(n, m-1) + getPermuStack(n-1, m+1);
int main()
printf("The total count of stackout permutation is %d.",
getPermuStack(6, 0));
The total count of stackout permutation is 132.
-----------------------------------------------------
上面方法是可行的，但在实际编程中最好不要用递归，这样如果递归次数一多就容易造成栈溢出。你可以试下用较大的参数来调用你的函数，会造成runtime
而 且纯粹的递归会造成大量的重复计算：比如，你在计算getPermuStack(5, 5)的时候计算了getPermuStack(5,
4)，然后在计算getPermuStack(5,3)的时候又计算了一遍。当然可以通过动态规划的思想设置一个二维数组来记录计算结果，可是太消耗空
如果直观的方法就能很高效地解决问题的话，就不会有那么多人去从数学上求解了。
递归的致命缺点,也是优点就是把复杂的计算留给机器, 递归往往能迅速简洁的思维求出问题的解,
也许得到的算法是低效的.所以递归应该是一种懒人算法. 而"从数学上求解"应当是指从正向考虑问题的解,
递归是逆向求解.
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。卡塔兰数_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
阅读已结束，下载文档到电脑
想免费下载更多文档？
定制HR最喜欢的简历
你可能喜欢不同的路径
有一个机器人的位于一个M×N个网格左上角（下图中标记为'Start'）。
机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的...
题目描述：有一个机器人的位于一个M×N个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。问有多少条不同的路径？
跟之前的那道“最小路径和”（详见：点击打开链接）是一...
两种方法：
int sum(int m, int n)//递归
if (m == 1 || n == 1)
int total = sum(m - 1, ...
1个2*2的网格，从左上角到右下角有6条线路（不可回头），如图所示
请问，一个n*n的网格，从左上角到右下角有多少条线路。
把网格看做二维坐标，向下为正，向右为...
题目源自于leetcode。
题目：A robot is located at the top-left corner of a m x n grid (marked 'Start' in the d...
题目描述：
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram bel...
package Level2;
* Unique Paths
* A robot is located at the top-left corner of a m x n gr...
原文转自：http://blog.csdn.net/linhuanmars/article/details/，原文中有错别字，我就没有更改。如果作者对转载不满意，请联系我，修改至满意为...
题目描述现在有两个好友A和B，住在一片长有蘑菇的由n＊m个方格组成的草地，A在(1,1),B在(n,m)。现在A想要拜访B，由于她只想去B的家，所以每次她只会走(i,j+1)或(i+1,j)这样的路线...
他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)下次自动登录
现在的位置:
& 综合 & 正文
Catalan 数
Reference:
　　令h(0)=1,h(1)=1，catalan数满足递归式：
　　h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n&=2),这是n阶递推关系;
　　还可以化简为1阶递推关系: 如h(n)=(4n-2)/(n+1)*h(n-1)(n&1) h(0)=1
　　该递推关系的解为：h(n)=C(2n,n)/(n+1)=P(2n,n)/(n+1)!=(2n)!/(n!*(n+1)!) (n=1,2,3,...)
　　卡 塔兰数例的前几项为(sequence A 0 0 0 1 0 8 in OEIS) [注： n = 0, 1, 2, 3, … n]
　　1, 1, 2, 5, 14, 42, 132, 429, , 1, 0, 357670,
, , , , , , , 4, 2, …
　　我并不关心其解是怎么求出来的，我只想知道怎么用catalan数分析问题。
　　我总结了一下，最典型的三类应用：（实质上却都一样，无非是递归等式的应用，就看你能不能分解问题写出递归式了）
　　1.括号化问题。　
　　矩阵链乘： P=a0×a1×a2×a3×……×an，共有（n+1）项，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)
　　类似题目：有N个节点的二叉树共有多少种情形？
　　2.出栈次序问题。　
　　一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
　　类似题目：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
　　* * * *
　　* * * * *
　　形如这样的直角三角形网格，从左上角开始，只能向右走和向下走，问总共有多少种走法？
　　问题的由来：编号为 1 到 n 的 n 个元素，顺序的进入一个栈，则可能的出栈序列有多少种？
　　对问题的转化与思考：n 个元素进栈和出栈，总共要经历 n 次进栈和 n 次出栈。这就相当于对这 2n 步操作进行排列。
　　一个模型：一个 n*n 的正方形网格，从左上角顶点到右下角顶点，只能向右走和向下走。问共有多少种走法。如果将向右走对应上述问题的出栈，向下走对应上述问题的进栈，那么，可 以视此模型为对上述问题的具体描述。而解决此问题，只要在总共从左上角到右下角的2n步中，选定向右走的步数，即共有C(n
2n)中走法。
　　但是存在一个问题，如果走法越过了对角线，那么对应到上述问题是出栈数比入栈数多，这是不符合实际的。
　　对以上模型进行处理，对角线将以上正方形网格分成两部分，只留下包含对角线在内的下半部分，那么就不会出现越过对角线的问题。而这问题就是开始提出的问题。
　　-------------------------------------------------------
　　问题等价于：n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？
　　解答： 设P2n为这样所得的数的个数。在2n位上填入n个1的方案数为 C（n 2n）
　　不填1的其余n位自动填以数0。从C（n 2n）中减去不符合要求的方案数即为所求。
　　不合要求的数指的是从左而右扫描，出现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个1和n+1个0组成的一个排列。
　　反过来，任何一个 由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组成的2n位数，必对应于一个不合要求的数。
　　用上述方法建立了由n+1个0和n－1个1组成的2n位数，与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应。
　　是由4个0和4个1组成的8位2进制数。但从左而右扫描在第5位（显示为红色）出现0的累计数3超过1的累计数2，它对应于由3个1，5个0组成的。
　　反过来
　　对应于
　　因而不合要求的2n位数与n+1个0，n－1个1组成的排列一一对应，故有
　　P2n = C（n 2n）— C（n+1 2n）
　　这个结果是一个“卡塔兰数”Catalan
　　3.将多边行划分为三角形问题。
　　将一个凸多边形区域分成三角形区域的方法数?
　　类似题目：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他
　　从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
　　类似题目：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
&&&&推荐文章:
【上篇】【下篇】【答案】九章算法面试题26 方格取数_九章算法_传送门
【答案】九章算法面试题26 方格取数
初阶：有一个n*m的矩阵，需要从坐上角(1,1)走到右下角(n,m)，只能向右和向下走。矩阵中的每个方格有一个非负整数，问从左上角到右下角的所有路径中，数字之和最大的路径是哪一条。进阶：如果可以从左上角往下走k次，每个方格中的数被取走之后第二次经过则不再累加数值。请问走k次最多能取到的数值之和是多少。答：初阶：采用动态规划算法。F[i][j]代表从左上角到(i,j)这个位置的最大路径和。有F[i][j] = max{F[i-1][j], F[i][j-1]} + A[i][j]。其中A[i][j]为(i,j)这个格子中的数值。答案为F[n][m]。时间复杂度O(n*m)。进阶：采用网络流算法。将每个格子拆为两个点——入点和出点，入点到出点之间的流量限制为1，费用为格子的数值。所有出点均向它右方和下方的入点连一条流量限制为无穷大，费用为0的边。连接源点到左上角入点，流量设为k，费用设为0。设右下角的出点为汇点。从源点到汇点做一次最小费用最大流算法，即可得到答案。面试官角度：初阶问题是经常会被问到的问题。也是必须要掌握的动态规划算法问题之一。类似的题目有数字三角形。进阶问题一般不会被问到，在北美的面试中基本没有被问到过。再国内的面试中，有一些公司很牛但招聘名额很少时会问到这个题目，笔者曾经在参加面试时被问到的这个题。一般来说网络流算法不会在面试中被问到，所以读者不用担心也不必准备此类问题。只需要掌握初阶问题这种最基本的动态规划算法即可。#动态规划##网络流#
觉得不错，分享给更多人看到
九章算法 微信二维码
分享这篇文章
九章算法 最新头条文章
九章算法 热门头条文章