通过高新区网站建设,织梦能不能做门户网站,模板ppt,怎么制作商城小程序文章目录1、简介1.1 何为卡特兰数1.2 卡特兰数的通项公式2、应用2.1 题目1#xff1a;括号合法题目描述思路分析2.2 题目2#xff1a;进出栈的方式2.2.1 题目描述2.2.2 思路分析2.3 题目3#xff1a;合法的序列2.3.1 题目描述2.3.2 思路分析2.3.3 代码实现2.4 题目4#xf…
文章目录1、简介1.1 何为卡特兰数1.2 卡特兰数的通项公式2、应用2.1 题目1括号合法题目描述思路分析2.2 题目2进出栈的方式2.2.1 题目描述2.2.2 思路分析2.3 题目3合法的序列2.3.1 题目描述2.3.2 思路分析2.3.3 代码实现2.4 题目4不同二叉树的数量2.4.1 题目描述2.4.2 思路分析2.4.3 代码实现3、总结1、简介
1.1 何为卡特兰数
卡特兰数又称卡塔兰数英文名Catalan number是组合数学 中一个常在各种计数问题中出现的数列。
前几项为1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …
1.2 卡特兰数的通项公式
k(0)1,k(1)1k(0) 1, k(1) 1k(0)1,k(1)1 时如果接下来的项满足
k(n)k(0)∗k(n−1)k(1)∗k(n−2)...k(n−2)∗k(1)k(n−1)∗k(0)k(n) k(0) * k(n - 1) k(1) * k(n - 2) ... k(n - 2) * k(1) k(n - 1) * k(0)k(n)k(0)∗k(n−1)k(1)∗k(n−2)...k(n−2)∗k(1)k(n−1)∗k(0)
或者
k(n)C2nn−C2nn−1k(n) C_{2n}^n- C_{2n}^{n-1}k(n)C2nn−C2nn−1
或者
k(n)C2nn/(n1)k(n) C_{2n}^n / (n 1)k(n)C2nn/(n1)
就说这个表达式满足卡特兰数常用的是范式1和23几乎不会使用到
2、应用
2.1 题目1括号合法
题目描述
给定 NNN 个左括号NNN 个右括号它们自由组合必须全部使用能得到多少个合法的组合
思路分析
“合法”的定义是对于自由排列的组合只要保证任意的前缀右括号数量 ≤\le≤ 左括号数量那么它最终一定是合法的。原理就是左括号比右括号多的时候一旦出现右括号就能将多的左括号配对最终一定会全部配对成功。反之则不行。
先讨论一个数学思想如何确定两个集合相等
【集合A 和 集合B 可以是完全不相干的两个可数集合只要能找到一个映射fff使得A集合中的一个对应B集合中的一个又能找到一个和 fff 毫不相干的映射 ggg 使得 B集合中的一个对应 A集合中的一个如果存在这样一组映射那么A集合数量和B集合数量一定相等。】
借此来讨论括号组合的合法问题。合法的组合数量不好算那就可以先选出不合法的组合数量然后使用总的排列方法 减去 不合法的就是合法的。
总的排列方法数为 C2nnC_{2n}^nC2nn意思是一共 2n2n2n 个位置选择其中的 nnn 个放左括号剩下的 nnn 个位置放右括号。
而不合法的特征一定存在一个最初的前缀右括号数量 左括号数量 1如 ())(()最初前缀就是 ())。那么在该前缀后的就是 右括号数量 1 左括号数量 因为左右括号的数量相等。以这个最初前缀为分界线后面的所有括号进行反转即右括号变成左括号左括号变成右括号就变成了())))(那么分界线后的左括号数量 1 右括号数量。如此一来整体的 右括号数量 左括号数量 2。
定义两个集合A集合放所有不合法的情况B集合是 n1n 1n1 个右括号n−1n-1n−1个左括号 组合得到的所有情况 该集合的来源不深究也就是说通过上面的括号反转A集合中任意一个不合法的元素通过该映射都能变出一个B集合的某一个元素而B集合中的每个元素都能变成A集合其中的一个如))))((最初的不合法前缀为)以该前缀为分界线后面的所有括号反转。最终得到)((())。
所以 “nnn 个左括号 和 nnn 个右括号组合不合法的数量” “n1n1n1个右括号 和 n−1n-1n−1个左括号组合的所有数量”即 C2nn1C_{2n}^{n1}C2nn1。
所以nnn 个左括号和 nnn 个右括号组合的合法数量 C2nn−C2nn1C_{2n}^{n} - C_{2n}^{n1}C2nn−C2nn1而 C2nn1C2nn−1C_{2n}^{n1} C_{2n}^{n-1}C2nn1C2nn−1因此合法的组合数量也可以是 C2nn−C2nn−1C_{2n}^n - C_{2n}^{n-1}C2nn−C2nn−1。
也就是说括号类型的违规可以转换为卡特兰数进行计算因为C2nn−C2nn−1C_{2n}^n - C_{2n}^{n-1}C2nn−C2nn−1 是卡特兰数的通项公式之一。
2.2 题目2进出栈的方式
2.2.1 题目描述
nnn 个数字要进出栈一共有多少种进出栈的方式
2.2.2 思路分析
例如给定数字[1, 2]进出栈的方式
合法的情况
1. 1进(↓1出(↑)2进(↓)2出(↑)
2. 1进(↓)2进(↓)2出(↑)1出(↑)
只用记录箭头不合法的情况
1. ↑ ↑ ↓ ↓ 没有数字进栈是无法出栈的考察箭头组合的合法数量这其实就是括号问题。进栈是左括号出栈是右括号。合法的条件就是在任何时候右括号数量不能大于左括号数量也就是任意时刻出栈次数 ≤\le≤ 进栈次数就是合法的进出栈方式就是卡特兰数。
再举个例子某个公司的股票有上涨和下跌问有多少种交易方式可以使得股票不会跌到X轴以下 这也是一个卡特兰数问题往上就是左括号往下就是右括号就是在问左右括号合理的结合方式。
2.3 题目3合法的序列
2.3.1 题目描述
假设给你 NNN 个 0和 NNN 个 1你必须用全部数字拼序列。
返回有多少个序列满足任何前缀串1的数量都不少于0的数量
2.3.2 思路分析
这个就是 “括号合法” 模型问题1是左括号0是右括号任意时刻满足左括号数量 ≥\ge≥ 右括号数量。
直接使用卡特兰数的通项公式解决即可。
2.3.3 代码实现
import java.util.LinkedList;public class 10Ways {//方法1暴力递归public static long ways1(int N) {int zero N;int one N;LinkedListInteger path new LinkedList();LinkedListLinkedListInteger ans new LinkedList();process(zero, one, path, ans);long count 0;for (LinkedListInteger cur : ans) {int status 0;for (Integer num : cur) {if (num 0) {status;} else {status--;}if (status 0) {break;}}if (status 0) {count;}}return count;}public static void process(int zero, int one, LinkedListInteger path, LinkedListLinkedListInteger ans) {if (zero 0 one 0) {LinkedListInteger cur new LinkedList();for (Integer num : path) {cur.add(num);}ans.add(cur);} else {if (zero 0) {path.addLast(1);process(zero, one - 1, path, ans);path.removeLast();} else if (one 0) {path.addLast(0);process(zero - 1, one, path, ans);path.removeLast();} else {path.addLast(1);process(zero, one - 1, path, ans);path.removeLast();path.addLast(0);process(zero - 1, one, path, ans);path.removeLast();}}}//方法2卡特兰数的通项公式解决public static long ways2(int N) {if (N 0) {return 0;}if (N 2) {return 1;}long a 1;long b 1;long limit N 1;for (long i 1; i limit; i) {if (i N) {a * i;} else {b * i;}}return (b / a) / (N 1);}public static void main(String[] args) {System.out.println(test begin);for (int i 0; i 10; i) {long ans1 ways1(i);long ans2 ways2(i);if (ans1 ! ans2) {System.out.println(Oops!);}}System.out.println(test finish);}
}2.4 题目4不同二叉树的数量
2.4.1 题目描述
有 NNN 个二叉树节点每个节点彼此之间无任何差别。返回由 NNN 个二叉树节点组成的不同结构数量是多少
2.4.2 思路分析
如果 0 个节点只能组成空树1种 如果 1 个节点只能组成1个节点的树1种 如果 2 个节点只有2种结构。
n 个节点组成二叉树的情况
1第 1 种划分头结点1个左子树0个右子树 n−1n-1n−1 个 在这种划分下不同结构的数量为[0个节点组成的方法数] ×\times× [n−1n-1n−1个节点组成的方法数]
2第 2 种划分头结点左边1个节点右边 n−2n-2n−2 个节点 在这种划分下不同结构的数量为[1个节点组成的方法数] ×\times× [n−2n-2n−2个节点组成的方法数]
这个规律就是卡特兰数的第1个通项公式所以这就是卡特兰数。 那么直接用卡特兰数的第2个通项公式计算即可因为卡特兰数的三个通项公式是等效的。
2.4.3 代码实现
public class DifferentBTNum {// k(0) 1, k(1) 1
//
// k(n) k(0) * k(n - 1) k(1) * k(n - 2) ... k(n - 2) * k(1) k(n - 1) * k(0)
// 或者
// k(n) c(2n, n) / (n 1)
// 或者
// k(n) c(2n, n) - c(2n, n-1)//方法1public static long num1(int N) {if (N 0) {return 0;}if (N 2) {return 1;}long[] dp new long[N 1];dp[0] 1;dp[1] 1;for (int i 2; i N; i) {for (int leftSize 0; leftSize i; leftSize) {dp[i] dp[leftSize] * dp[i - 1 - leftSize];}}return dp[N];}//方法2卡特兰数public static long num2(int N) {if (N 0) {return 0;}if (N 2) {return 1;}long a 1;long b 1;for (int i 1, j N 1; i N; i, j) {a * i;b * j;long gcd gcd(a, b);a / gcd;b / gcd;}return (b / a) / (N 1);}public static long gcd(long m, long n) {return n 0 ? m : gcd(n, m % n);}public static void main(String[] args) {System.out.println(test begin);for (int i 0; i 15; i) {long ans1 num1(i);long ans2 num2(i);if (ans1 ! ans2) {System.out.println(Oops!);}}System.out.println(test finish);}
}3、总结
要对卡特兰数的通项公式1和公式2烂熟于心对“括号合法”模型左右括号数量相等的合法性问题要有敏感度加强对卡特兰数通项公式1的敏感度的训练如题目4符合公式1等同于公式2而通常可能是写出了暴力递归才会发现公式1就要求对暴力解法有了解。
补充
数学结论所有整数和所有偶数数量相等。因为任何整数乘以2后等于某个偶数而任意偶数除以2后等于某个整数二者建立了一一映射关系所以整数数量和偶数数量就是一样多的。在数学上它叫作“等势”。
5米的线和10米的线上的点数量一样多。在两条线之外找某一个定点5米线上找任意一个点和定点连线能对应到10米中的一个点10米的任意一个点和定点连线能对应到5米中的一个点所以5米的线和10米的线点一样多。 点是无长度的无长度的东西有可能有无限个点。更多可以查看希尔伯特旅馆悖论。
总而言之牵扯到一个非常重要的思想两个可数集合A和B能互相建立一种映射关系那它们的数量就是一样多的。 文章转载自： http://www.morning.mkxxk.cn.gov.cn.mkxxk.cn http://www.morning.ryrpq.cn.gov.cn.ryrpq.cn http://www.morning.mxnfh.cn.gov.cn.mxnfh.cn http://www.morning.rszyf.cn.gov.cn.rszyf.cn http://www.morning.btwlp.cn.gov.cn.btwlp.cn http://www.morning.wnjrf.cn.gov.cn.wnjrf.cn http://www.morning.jgttx.cn.gov.cn.jgttx.cn http://www.morning.rbylq.cn.gov.cn.rbylq.cn http://www.morning.jcxgr.cn.gov.cn.jcxgr.cn http://www.morning.kbqbx.cn.gov.cn.kbqbx.cn http://www.morning.thrtt.cn.gov.cn.thrtt.cn http://www.morning.lsyk.cn.gov.cn.lsyk.cn http://www.morning.gwqq.cn.gov.cn.gwqq.cn http://www.morning.ymqrc.cn.gov.cn.ymqrc.cn http://www.morning.sfdky.cn.gov.cn.sfdky.cn http://www.morning.rknsp.cn.gov.cn.rknsp.cn http://www.morning.wtdhm.cn.gov.cn.wtdhm.cn http://www.morning.rhfbl.cn.gov.cn.rhfbl.cn http://www.morning.djxnw.cn.gov.cn.djxnw.cn http://www.morning.fynkt.cn.gov.cn.fynkt.cn http://www.morning.sbrxm.cn.gov.cn.sbrxm.cn http://www.morning.mkczm.cn.gov.cn.mkczm.cn http://www.morning.gqfks.cn.gov.cn.gqfks.cn http://www.morning.kmqlf.cn.gov.cn.kmqlf.cn http://www.morning.ykmtz.cn.gov.cn.ykmtz.cn http://www.morning.rckmz.cn.gov.cn.rckmz.cn http://www.morning.hclplus.com.gov.cn.hclplus.com http://www.morning.ygkk.cn.gov.cn.ygkk.cn http://www.morning.xqbgm.cn.gov.cn.xqbgm.cn http://www.morning.mzqhb.cn.gov.cn.mzqhb.cn http://www.morning.kqqk.cn.gov.cn.kqqk.cn http://www.morning.dskzr.cn.gov.cn.dskzr.cn http://www.morning.qmbtn.cn.gov.cn.qmbtn.cn http://www.morning.cwqln.cn.gov.cn.cwqln.cn http://www.morning.wlbwp.cn.gov.cn.wlbwp.cn http://www.morning.glnxd.cn.gov.cn.glnxd.cn http://www.morning.nzfqw.cn.gov.cn.nzfqw.cn http://www.morning.yrflh.cn.gov.cn.yrflh.cn http://www.morning.hcrxn.cn.gov.cn.hcrxn.cn http://www.morning.nlbhj.cn.gov.cn.nlbhj.cn http://www.morning.yrhpg.cn.gov.cn.yrhpg.cn http://www.morning.ylkkh.cn.gov.cn.ylkkh.cn http://www.morning.ndmbz.cn.gov.cn.ndmbz.cn http://www.morning.qgtbx.cn.gov.cn.qgtbx.cn http://www.morning.zhiheliuxue.com.gov.cn.zhiheliuxue.com http://www.morning.qkgwx.cn.gov.cn.qkgwx.cn http://www.morning.pqkyx.cn.gov.cn.pqkyx.cn http://www.morning.smygl.cn.gov.cn.smygl.cn http://www.morning.ykyfq.cn.gov.cn.ykyfq.cn http://www.morning.hfytgp.cn.gov.cn.hfytgp.cn http://www.morning.hpkr.cn.gov.cn.hpkr.cn http://www.morning.swkzr.cn.gov.cn.swkzr.cn http://www.morning.mhrzd.cn.gov.cn.mhrzd.cn http://www.morning.qjsxf.cn.gov.cn.qjsxf.cn http://www.morning.wtsr.cn.gov.cn.wtsr.cn http://www.morning.qqhmg.cn.gov.cn.qqhmg.cn http://www.morning.stwxr.cn.gov.cn.stwxr.cn http://www.morning.nyfyq.cn.gov.cn.nyfyq.cn http://www.morning.yltnl.cn.gov.cn.yltnl.cn http://www.morning.kndt.cn.gov.cn.kndt.cn http://www.morning.mqwnz.cn.gov.cn.mqwnz.cn http://www.morning.ncfky.cn.gov.cn.ncfky.cn http://www.morning.ghphp.cn.gov.cn.ghphp.cn http://www.morning.ahscrl.com.gov.cn.ahscrl.com http://www.morning.jwbfj.cn.gov.cn.jwbfj.cn http://www.morning.nkbfc.cn.gov.cn.nkbfc.cn http://www.morning.czzpm.cn.gov.cn.czzpm.cn http://www.morning.jyznn.cn.gov.cn.jyznn.cn http://www.morning.rqxch.cn.gov.cn.rqxch.cn http://www.morning.cszbj.cn.gov.cn.cszbj.cn http://www.morning.qfbzj.cn.gov.cn.qfbzj.cn http://www.morning.wwznd.cn.gov.cn.wwznd.cn http://www.morning.gypcr.cn.gov.cn.gypcr.cn http://www.morning.mumgou.com.gov.cn.mumgou.com http://www.morning.frpfk.cn.gov.cn.frpfk.cn http://www.morning.nmbbt.cn.gov.cn.nmbbt.cn http://www.morning.tphrx.cn.gov.cn.tphrx.cn http://www.morning.ldspj.cn.gov.cn.ldspj.cn http://www.morning.pmrlt.cn.gov.cn.pmrlt.cn http://www.morning.tfei69.cn.gov.cn.tfei69.cn
