算法 卡特兰数

卡特兰数

卡特兰数简介

卡特兰数推荐博文

卡特兰数是组合数学中的一种著名数列,通常用如下通项式表示(为了不与组合数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)

  1. 给定节点组成二叉搜索树

    给定N个节点,能构成多少种不同的二叉搜索树?(f(n)种)

  2. 扩号化

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

  3. 出栈次序

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

  4. 凸多边形三角划分

    在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数f(n)。

  5. n对括号正确匹配数目

    给定n对括号,求括号正确配对的字符串数

  6. 霍比特人和兽人排队买票问题 (下文矩阵II问题)

题目描述

宁宁考虑的是这样一个问题:一个操作数序列,1,2,…,n(图示为 1 到 3 的情况),栈 A 的深度大于 n。

现在可以进行两种操作,

  1. 将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作)
  2. 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作)

使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由 1 2 3 生成序列 2 3 1 的过程。

(原始状态如上图所示)

你的程序将对给定的 n,计算并输出由操作数序列 1,2,…,n 经过操作可能得到的输出序列的总数。

输入格式

输入文件只含一个整数 n(1≤n≤18)。

输出格式

输出文件只有一行,即可能输出序列的总数目。

输入 #1

1
3

输出 #1

1
5
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main(){
int a[110]={1},n,t,i,j;
cin>>n;
for(i=1;i<=n;i++){
for(j=0;j<i;j++){
a[i] += a[j] * a[i-j-1];
}
}
cout<<a[n];
return 0;
}

矩阵II

Problem

众所周知,在中国古代算筹中,红为正,黑为负……

给定一个1(2n)的矩阵(usqwedf:这不是一个2n的队列么),现让你自由地放入红色算筹和黑色算筹,使矩阵平衡[即对于所有的i(1<=i<=2n),*使第1~i格中红色算筹个数大于等于黑色算筹]**

问有多少种方案满足矩阵平衡。

输入 #1

1
2 1<=n<=100

输出 #1

1
2  方案数t对100取模
1
2
3
4
5
6
7
8
9
10
11
12
int main(){
int a[110]={1},n,t,i,j;
cin>>n;
for(i=1;i<=n;i++){
for(j=0;j<i;j++){
a[i] += a[j] * a[i-j-1];
a[i] %= 100
}
}
cout<<a[n];
return 0;
}

鸡蛋饼

题目描述

最近小 x 又发现了一个关于圆的有趣的问题:在圆上有 2N 个不同的点,小 x 想用 N 条线段把这些点连接起来(每个点只能连一条线段), 使所有的线段都不相交,他想知道这样的连接方案有多少种?

输入格式

有且仅有一个正整数 N 。 (N≤2999)

输出格式

要求的方案数(结果 mod100000007)。

输入 #1

1
24

输出 #1

1
4057031
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*那么假如我们在圆上画了2n个点,顺时针编号为1,2,3,4……,你便会发现,如果一个奇数点和另一个奇数点相连,一定会造成将剩下所没有连线的点分在两边的都是奇数个,而后两边必定有一个点没线连或穿越其中的一条线,那么就不可能完成了。那么我们可以把奇数点看成左括号,偶数点看成右括号,然后把圆切开,就变成了一个括号匹配的方案数问题。为什么圆可以切开呢?因为A连B和B连A是同一种切法。
在这里可以用h(n)=C(2n,n)/(n+1),用扩展欧几里德求逆元。
*/
int main(){
int a[3100]={1},n,t,i,j;
for(i=1;i<=n;i++){
for(j=0;j<i;j++){
a[i] += a[j] * a[i-j-1];
a[i] %= 100000007
}
}
cout<<a[n];
return 0;
}

树屋阶梯

题目描述:

暑假期间,小龙报名了一个模拟野外生存作战训练班来锻炼体魄,训练的第一个晚上,教官就给他们出了个难题。由于地上露营湿气重,必须选择在高处的树屋露营。小龙分配的树屋建立在一颗高度为N+1尺(N为正整数)的大树上,正当他发愁怎么爬上去的时候,发现旁边堆满了一些空心四方钢材(如图1.1),经过观察和测量,这些钢材截面的宽和高大小不一,但都是1尺的整数倍,教官命令队员们每人选取N个空心钢材来搭建一个总高度为N尺的阶梯来进入树屋,该阶梯每一步台阶的高度为1尺,宽度也为1尺。如果这些钢材有各种尺寸,且每种尺寸数量充足,那么小龙可以有多少种搭建方法?(注:为了避免夜里踏空,钢材空心的一面绝对不可以向上。)

输入格式:

一个正整数 N(1≤N≤500),表示阶梯的高度

输出格式:

一个正整数,表示搭建方法的个数。(注:搭建方法个数可能很大。)

输入样例:

3

输出样例:

5

思路:

这里有 N 个拐角,而题目只允许我们放 N 个矩形,也就是说,每个矩形恰好覆盖一个拐角。从而分为上和右两个问题,从而递归解决

1
2
3
4
5
6
7
8
9
10
# 卡特兰数递推公式: h(n)= (2n)! / ((n+1)!⋅n!)
#引用math库
import math
#定义组合数函数
def C(n,m):
return math.factorial(n)//math.factorial(m)//math.factorial(n-m)
#引用阶乘求组合数 //为地板除 返回int 向下取整
#而如果用/则会返回float导致其他问题
n=int(input())
print(C(2*n,n)-C(2*n,n-1))