卡特兰数的实现与应用

比眉伴天荒 2022-05-28 12:24 182阅读 0赞

这是在解决给定节点树，可以构成多少二叉树时遇到的问题，我还真的就都画了出来！！这个问题其实就是卡特兰数的一种应用而已。

卡特兰数 又称卡塔兰数，英文名Catalan number，是[组合数学][Link 1]中一个常出现在各种计数问题中出现的[数列][Link 2]。就是1,1,2,5,14,.......

原理：令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)**

int Catlan(int n)//计算第n位catlan数，(n = 0,1,..)
    {
    	int num_1 = 2 * n;
    	int num_2 = n;
    
    	for (int i = 1; i< n; ++i)
    	{
    		num_1 = num_1 * (2 * n - i);
    		num_2 = num_2 * (n - i);
    	}
    	int num = num_1 / num_2;//计算C(n,2n)
    	int Catlan_num = num / (n + 1);
    	
    	return Catlan_num;
    }

应用：

**1：****括号化**

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

**2：出栈次序**

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

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

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

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

**5:n对括号正确匹配数目**

给定n对括号，求括号正确配对的字符串数，例如：

**6:**在[圆上][Link 7]选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？

**7:**一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？

[Link 1]: https://baike.baidu.com/item/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6
[Link 2]: https://baike.baidu.com/item/%E6%95%B0%E5%88%97
[Link 3]: https://baike.baidu.com/item/%E8%BF%9B%E6%A0%88
[Link 4]: https://baike.baidu.com/item/%E5%87%BA%E6%A0%88
[Link 5]: https://baike.baidu.com/item/%E8%8A%82%E7%82%B9
[Link 6]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91
[Link 7]: https://baike.baidu.com/item/%E5%9C%86%E4%B8%8A