算法 卡特兰数
卡特兰数
卡特兰数简介
卡特兰数是组合数学中的一种著名数列,通常用如下通项式表示(为了不与组合数C冲突,本文用f表示卡特兰数):
f(n)=C(n、2n)/(n+1)
当然,卡特兰数也是有递推式的:
f(n)=∑(n−1、i=0)f(i)×f(n−i−1)
但在实际应用中,最常用的却是第一个通项式的变形:
f(n)=C(n、2n)−C(n−1、2n)
给定节点组成二叉搜索树
给定N个节点,能构成多少种不同的二叉搜索树?(f(n)种)
扩号化
矩阵连乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(f(n)种)
出栈次序
一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?(f(n)种)
凸多边形三角划分
在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数f(n)。
n对括号正确匹配数目
给定n对括号,求括号正确配对的字符串数
霍比特人和兽人排队买票问题 (下文矩阵II问题)
栈
题目描述
宁宁考虑的是这样一个问题:一个操作数序列,1,2,…,n(图示为 1 到 3 的情况),栈 A 的深度大于 n。
现在可以进行两种操作,
- 将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作)
- 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作)
使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由 1 2 3
生成序列 2 3 1
的过程。
(原始状态如上图所示)
你的程序将对给定的 n,计算并输出由操作数序列 1,2,…,n 经过操作可能得到的输出序列的总数。
输入格式
输入文件只含一个整数 n(1≤n≤18)。
输出格式
输出文件只有一行,即可能输出序列的总数目。
输入 #1
1 | 3 |
输出 #1
1 | 5 |
1 |
|
矩阵II
Problem
众所周知,在中国古代算筹中,红为正,黑为负……
给定一个1(2n)的矩阵(usqwedf:这不是一个2n的队列么),现让你自由地放入红色算筹和黑色算筹,使矩阵平衡[即对于所有的i(1<=i<=2n),*使第1~i格中红色算筹个数大于等于黑色算筹]**
问有多少种方案满足矩阵平衡。
输入 #1
1 | 2 1<=n<=100 |
输出 #1
1 | 2 方案数t对100取模 |
1 | int main(){ |
鸡蛋饼
题目描述
最近小 x 又发现了一个关于圆的有趣的问题:在圆上有 2N 个不同的点,小 x 想用 N 条线段把这些点连接起来(每个点只能连一条线段), 使所有的线段都不相交,他想知道这样的连接方案有多少种?
输入格式
有且仅有一个正整数 N 。 (N≤2999)
输出格式
要求的方案数(结果 mod100000007)。
输入 #1
1 | 24 |
输出 #1
1 | 4057031 |
1 | /*那么假如我们在圆上画了2n个点,顺时针编号为1,2,3,4……,你便会发现,如果一个奇数点和另一个奇数点相连,一定会造成将剩下所没有连线的点分在两边的都是奇数个,而后两边必定有一个点没线连或穿越其中的一条线,那么就不可能完成了。那么我们可以把奇数点看成左括号,偶数点看成右括号,然后把圆切开,就变成了一个括号匹配的方案数问题。为什么圆可以切开呢?因为A连B和B连A是同一种切法。 |
树屋阶梯
题目描述:
暑假期间,小龙报名了一个模拟野外生存作战训练班来锻炼体魄,训练的第一个晚上,教官就给他们出了个难题。由于地上露营湿气重,必须选择在高处的树屋露营。小龙分配的树屋建立在一颗高度为N+1尺(N为正整数)的大树上,正当他发愁怎么爬上去的时候,发现旁边堆满了一些空心四方钢材(如图1.1),经过观察和测量,这些钢材截面的宽和高大小不一,但都是1尺的整数倍,教官命令队员们每人选取N个空心钢材来搭建一个总高度为N尺的阶梯来进入树屋,该阶梯每一步台阶的高度为1尺,宽度也为1尺。如果这些钢材有各种尺寸,且每种尺寸数量充足,那么小龙可以有多少种搭建方法?(注:为了避免夜里踏空,钢材空心的一面绝对不可以向上。)
输入格式:
一个正整数 N(1≤N≤500),表示阶梯的高度
输出格式:
一个正整数,表示搭建方法的个数。(注:搭建方法个数可能很大。)
输入样例:
3
输出样例:
5
思路:
这里有 N 个拐角,而题目只允许我们放 N 个矩形,也就是说,每个矩形恰好覆盖一个拐角。从而分为上和右两个问题,从而递归解决
1 | # 卡特兰数递推公式: h(n)= (2n)! / ((n+1)!⋅n!) |