数据结构—出栈排列个数计算法（卡特兰数）-创新互联

这里先摆上传统结论：

看不懂没关系，接下来我会用直截了当（歪门邪道）的方法帮助大家理解。

首先，n 代表进栈的元素数量。

例入a,b,c三个元素进栈，则n为3 。

2n 与 n 的关系可以理解为从 2n 这个数开始往前乘以 2n-n个递减1的数

如原式中，n＝3，则2n＝6，那就需要从6开始递减三次，每次-1，然后三个数相乘，也就是6*5*4；也可以理解为2n--，从2n开始，减的次数为n次，也就是2n*2n-1*2n-2。

上面这是式1.

求出这个式子只是第一步。

式2则是：

把C前式子中分母的n+1转化化成（n+1）的阶乘，原式n＝3，则要求4的阶乘也就是4*3*2*1

不需要理会上面的公式，只需要 式1/式2 就可以得出我们需要的出栈可能性总和。

例： 有a ，b ，c 三个元素进栈，则通过不同入栈操作可能得到的abc出栈的不同排列个数为？

首先，已知abc一共是三个元素，所以，n＝3, 2n＝6 ，则式1＝6*5*4，这是分子。

分母则是（n+1）！也就是4！也就是4*3*2*1；这是分母。【此处感叹号为阶乘的意思】

然后分子与分母组合，6*5*4 / 4*3*2*1 = 120/24 ＝ 5。

所以出栈元素不同排列的个数为5。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧