一道面试题到卡特兰数及其应用

快来打我* 2022-07-13 06:42 95阅读 0赞

> 绘画展览门票每张5元，如果有2n个人排队购票，每人一张，并且其中一半人恰有5元钱，另一半人恰有10元钱，而票房无零钱可找，那么如何将这2n个人排成一列，顺次购票，使得不至于因票房无零钱可找而耽误时间，应该采用什么算法解决呢？（分支限界法）

这个是卡特兰数的经典应用。那么，我们先来看一下卡特兰数是什么东西呢？

**Catalan数的定义：**

> 令h(1)=1，Catalan数满足递归式：h(n) = h(1)*h(n-1) + h(2)* h(n-2) + … +  
> h(n-1)\*h(1)，n>=2
> 
> 该递推关系的解为：h(n) = c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)

问题描述:

12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？

应用公式：c(2n, n)/(n+1)。

而c(12, 6)/7 = 12\*11\*10\*9\*8\*7/(7\*6\*5\*4\*3\*2) = 132

注意：c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)

--------------------

# 应用 #

**1、括号化**

矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？

h(n-1)种

**2、出栈次序**

一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?

输出序列的总数目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)=h(n)。

类似问题：

>     买票找零
> 
> 有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)

**3、凸多边形三角划分**

在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f（6）=14。

f（n）=h（n-2） （n=2，3，4，……）

类似问题：

> 一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
> 
> 在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？

**4、给定节点组成二叉搜索树**

给定N个节点，能构成多少种不同的二叉搜索树？

（能构成h（N）个） （这个公式的下标是从h(0)=1开始的）

--------------------

求卡特兰数代码如下：

void catalan() //求卡特兰数
    {
        int i, j, len, carry, temp;
        a[1][0] = b[1] = 1;
        len = 1;
        for(i = 2; i <= 100; i++)
        {
            for(j = 0; j < len; j++) //乘法
            a[i][j] = a[i-1][j]*(4*(i-1)+2);
            carry = 0;
            for(j = 0; j < len; j++) //处理相乘结果
            {
                temp = a[i][j] + carry;
                a[i][j] = temp % 10;
                carry = temp / 10;
            }
            while(carry) //进位处理
            {
                a[i][len++] = carry % 10;
                carry /= 10;
            }
            carry = 0;
            for(j = len-1; j >= 0; j--) //除法
            {
                temp = carry*10 + a[i][j];
                a[i][j] = temp/(i+1);
                carry = temp%(i+1);
            }
            while(!a[i][len-1]) //高位零处理
            len --;
            b[i] = len;
        }
    }