算法中的数学---卡特兰数（解析+代码实现）

ゝ一纸荒年。 2022-12-04 01:20 13阅读 0赞

卡特兰数又称卡塔兰数，是组合数学中一种常出现于各种计数问题中的数列。

### 卡特兰数 ###

*  一、简单介绍
 *  二、应用
 *   *  2.1进出栈问题
     *  2.2排队方式
     *  2.3二叉树生成问题
     *  2.4凸多边形三角形划分
     *  2.5括号匹配问题
     *  2.6满二叉树个数
     *  2.7圆划分问题
     *  2.8填充问题

# 一、简单介绍 #

卡特兰数是一个数列，其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …  
卡特兰数满足如下递推关系：

![在这里插入图片描述][20200904214920907.gif_pic_center]  
其中 C n C\_\{n\} Cn表示数列的第n项。根据上述第一个式子我们可以推出：  
![在这里插入图片描述][20200904215427123.gif_pic_center]  
第二个推导式用于编程实现卡特兰数。

# 二、应用 #

## 2.1进出栈问题 ##

【问题描述】  
  1， 2， 3， 4依次进栈，则可能的一种进出栈顺序为：  
1in->2in->2out->3in->4in->4out->3out->1out，所以出栈顺序为：2431，那么请问按照1， 2， 3， 4，…， n依次进栈，出栈顺序种数h(n)为多少？  
【问题分析】  
  对n个数，假设**数k**最后一个出栈，k有n种可能，即每一个数都有可能最后出栈，我们算出每一种可能各有多少种情况，最后相加即可。  
  因为k最后一个出栈，而进栈顺序又是从小到大来的，所以**k前面的k-1个数在k进栈以前就已经全部出栈了，我们把前面k-1个数看出一个整体，那么全面k-1个数的出栈情况实际上就有h(k-1)种。**  
  **在k进栈之后，比k大的n-k个数才能进栈，但是它们又比k早出栈，把这n-k个数同样看成一个整体，共有h(n-k)种可能。** 二者综合一下，当数k最后出栈时，一共有h(k-1)h(n-k)种可能，k从1取到n，再把每种可能相加即得到最终答案：

![在这里插入图片描述][20200905100342610.gif_pic_center]  
  简而言之就是数k把这段序列分成了两部分：比k大的部分和比k小的部分。因为中间有k隔着，而它们又必须按照从小到大的次序进栈，所以这两部分进出栈是相互不影响的。  
  **很明显可以看出，该表达式就是卡特兰数的递推式。**

## 2.2排队方式 ##

【问题描述】  
  n个人手拿5元，n个人手拿10元，他们去排队买东西，东西价值5元，老板没有零钱（老板必须用收取的5元钞票给支付10元的顾客找零钱），请问一共有多少种排队方式？  
【问题分析】  
  **将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈，** 实际上也就转换成了进出栈问题，答案也为h(n)。

## 2.3二叉树生成问题 ##

【问题描述】  
  有n个结点，请问总共能构成多少种不同的二叉树？  
【问题分析】  
  假设采用中序遍历，根节点第k个被访问，则根的左子树共有k-1个结点，右子树共有n-k个结点，k同样可以取1-n，这就与进出栈问题分析思路一致了，所以一共h(n)种。

## 2.4凸多边形三角形划分 ##

【问题描述】  
  一个凸的n边形，用直线连接它的两个顶点使之分成多个三角形，每条直线不能相交，问一共多少种方案？  
比如凸六边形的划分情况为：  
![在这里插入图片描述][20200905101644802.png_pic_center]  
h(6)=14。  
【问题分析】  
  我们将凸多边形顶点从p1一直编号到pn，以p1pn这条边为基准，任选一个数k（2<=k<=n-1），将p1，pk以及pn三点连接，构成了一个三角形。**该三角形把该凸边形划分成了两个凸边形，一边顶点为1 ~ k-1，另一边为k+1 ~ n，于是又回到了进出栈问题，所以答案依旧为：h(n)。**

## 2.5括号匹配问题 ##

【问题描述】  
由1对括号，可以组成一种合法括号序列：()。  
由2对括号，可以组成两种合法括号序列：()()、(())。  
由n对括号组成的合法括号序列一共有多少种？  
【问题分析】  
  考虑n对括号时的任意一种配对方案，最后一个右括号有唯一的与之匹配的左括号，于是有唯一的表示A(B)，其中A和B也是合法的括号匹配序列。  
  假设S(n)为n对括号的正确配对数目，那么有递推关系S(n)=S(0)S(n-1)+S(1)S(n-2) +…+S(n-1)S(0)，显然S(n)是卡特兰数。

## 2.6满二叉树个数 ##

【问题描述】  
  n+1个叶子的满二叉树个数为多少？  
【问题分析】  
  不再分析，答案为h(n)。

## 2.7圆划分问题 ##

【问题描述】  
  在圆上选2n个点，讲这些点成对连接起来，保证所有直线不相交，问一共多少种可能？  
【问题分析】  
  答案为h(n)。

## 2.8填充问题 ##

【问题描述】  
  n个长方形填充一个高度为n的阶梯状图像方法数为多少？  
【问题分析】  
  答案为h(n)。

代码实现：

#include<bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    
    const int maxn = 20;
    int n;
    ll f1[maxn], f2[maxn];
    ll f[maxn * 2][maxn];
    
    //公式1:
    int solve1() { 
        f1[0] = f1[1] = 1;
        cin >> n;
        for(int i = 2; i <= n; i++) { 
            for(int j = 0; j < i; j++) { 
                f1[i] += (f1[j] * f1[i-j-1]);   //f(n)=f(0)f(n-1)+f(1)f(n-2)+...+f(n-1)f(0) 
            }
        }
        printf("%lld\n",f1[n]);
        return 0;
    }
    
    //公式2:
    int solve2() { 
        f2[0] = f2[1] = 1;
        cin >> n;
        for(int i = 2; i <= n; i++)
        { 
            f2[i] += f2[i - 1] * (4 * i - 2) / (i + 1);  //f(n)=f(n-1)*(4*n-2)/(n+1)
        }
        printf("%lld\n", f2[n]);
        return 0;
    }
    
    //公式3:
    int solve3() { 
    	cin >> n;
        for(int i = 1; i <= 2 * n; i++) { 
            f[i][0] = f[i][i] = 1;
            for(int j = 1; j < i; j++) { 
                f[i][j] = f[i - 1][j] + f[i - 1][j - 1];     //f(n)=c(2n,n)/(n+1)
            }
        }
        printf("%lld",f[2 * n][n] / (n + 1));
        return 0;
    }
    
    int main() { 
    	solve1();
    	solve2();
    	solve3();
    	return 0;
    }

[20200904214920907.gif_pic_center]: /images/20221123/9ab8b574ab35432dae9357657f796127.png
[20200904215427123.gif_pic_center]: /images/20221123/df2cfd8f78804b969cdc931e05719a28.png
[20200905100342610.gif_pic_center]: /images/20221123/2b730e6e9da545a7aeec23ebd30735e6.png
[20200905101644802.png_pic_center]: /images/20221123/da4f2f0036bf45f18834ee38bf551a25.png