个人做网站和百家号赚钱,wordpress彩色,莲都区建设局门户网站,seo关键词挖掘工具卡特兰(Catalan)数列典型特征有一类如下#xff1a; 1. 可以分为两列 2. 每行从左向右依次递增#xff08;减#xff09;#xff0c;每列从上向下依次递增#xff08;减#xff09;
/*
2-10 标准二维表问题
问题为#xff1a;设n是一个正整数。2*n的标准二维表是由正…卡特兰(Catalan)数列典型特征有一类如下 1. 可以分为两列 2. 每行从左向右依次递增减每列从上向下依次递增减
/*
2-10 标准二维表问题
问题为设n是一个正整数。2*n的标准二维表是由正整数1,2,…2n组成的2*n数组该数组的每行从左到右递增每列从上到下递增。
把数字从小到大进行排序
用0表示对应的数字在第一排,用1表示对应的数字在第二排,那么含有n个0,n个1的序列,就对应一种方案.
比如000111就对应着
第一排1 2 3
第二排4 5 6
010101就对应着
第一排1 3 5
第二排2 4 6
问题转换为这样的满足条件的01序列有多少个。
任意的1前面统计在这个1之前的0和1的个数要求0的个数大于1的个数。显然有c(2n, n)个含01各n个的序列剩下的是计算不允许的序列数(它包含正确个数的0和1但是违背其它条件)。
在任何不允许的序列中定出使得1的个数超过0的个数的第一个1的位置。
然后在导致并包括这个1的部分序列中以0代替所有的1并以1代表所有的0。
结果是一个有(n1)个0和(n-1)个1的序列。
反过来对于(n1)个0和(n-1)个1组成的每个序列我们都能逆转这个过程而且找出导致它的前一种类型的不允许序列。
例如1101 0001 1000必然来自0010 1111 1000
这个对应说明不允许的序列的个数是c(2n, n-1)
因此an c(2n, n) - c(2n, n-1)。该问题就是卡特兰数列
卡特兰数列的公式为
h(n) h(0)*h(n-1)h(1)*h(n-2)...h(n-1)*h(0) ;n2;h[0]1,h[1]1;
h(n) C(2n,n)-C(2n,n-1)
h(n) C(2n,n)/(n1)
*/
int BivTable(int n)
{if (n 0)return 0;vectorunsigned long long vec(n1, 0);vec[0] 1;vec[1] 1;for (int i 2; i n1; i){for (int j 0; j i; j){vec[i] (vec[j] * vec[i - j - 1]);}}return vec[n];
}
int main()
{cout BivTable(6);return 0;
}
//输出 132
关于卡特兰数列更多的解释参考博客 https://blog.csdn.net/Hackbuteer1/article/details/7450250 https://blog.csdn.net/gentledongyanchao/article/details/55276731
