80.阿里巴巴一道笔试题
问题描述:
12 个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人
高,问排列方式有多少种?
这个笔试题,很 YD,因为把某个递归关系隐藏得很深。
/* 80.阿里巴巴一道笔试题 问题描述: 12 个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人 高,问排列方式有多少种? 刚开始没看出来 后来发现了 卡特兰数 引用别人的问题分析： 我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排. 用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案. 比如000000111111就对应着 第一排：0 1 2 3 4 5 第二排：6 7 8 9 10 11 010101010101就对应着 第一排：0 2 4 6 8 10 第二排：1 3 5 7 9 11 问题转换为，这样的满足条件的01序列有多少个。 求，0的个数大于1的个数。 如果把0看成入栈操作，1看成出栈操作，就是说给定6个元素，合法的入栈出栈序列有多少个。 这就是catalan数,这里只是用于栈， 等价地描述还有，二叉树的枚举、多边形分成三角形的个数、圆括弧插入公式中的方法数， 其通项是c(2n, n)/(n+1)。 c(2n, n)/(n+1)=c(2n,n)-c(2n,n-1) c(12, 6)/7 = 12*11*10*9*8*7/(7*6*5*4*3*2) = 132 */