卡特兰数学习
1,概念
卡特兰数(英语:Catalan number),又称卡塔兰数,明安图数。是组合数学中一种常出现于各种计数问题中的数列。它在不同的计数问题中频繁出现。
2,公式
卡特兰数的递推公式为:f(n) = f(0) * f(n - 1) + f(1) * f(n - 2) + ... + f(n - 1) * f(0),其中初始值f(0) = f(1) = 1。
这个数列的前几项为: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...。

3,卡特兰数代码实现
递归
int catalan1(int n)
{
if (n <= 1) return 1;int res = 0;
for (int i = 1; i <= n - 1; i++)
res += catalan1(i)*catalan1(n-i);return res;
}
非递归
int catalan2(int n)
{
if (n <= 1) return 1;int* h = new int[n];
h[0] = h[1] = 1;
for (int i = 2; i < n ; i++)
{
h[i] = 0;
for (int j = 0; j < i; j++)
h[i] += (h[j] * h[i - 1 - j]); //f[i]=f[0]*f[i-1]+f[1]*f[i-2]+...+f[i-1]*f[0]
}
int result = h[n-1];
delete[] h;
return result;}
4,卡特兰数的应用
对于卡特兰数的介绍,我们只知道了它是组合数学中的一种规律,并没有具体意义,是一个常见的数学规律。
对于卡特兰数的初步理解:有一些操作,这些操作有一定的限制,如一种操作数不能超过另一种操作数,或两种操作数不能有交集,求这些操作的合法数量。
应用1:出栈次序(进出栈问题)
【问题描述】
一个无穷大的栈,进展序列为1,2,3,......,n,问出栈顺序有多少种?
【问题分析】
设f(n)=序列个数为n的出栈序列种数。假定,从开始到栈第一次出空为止,这段过程中第一个出栈的序数是k,如果栈直到整个过程结束时,才为空,那么k=n;首次出空之前,第一个出栈序数k,将1~n的序列划分成两部分。其中一个是1~k-1,一共k-1个数;另一部分是k+1~n,一共n-k个数。
此时,我们把k看作是一个序数,根据乘法原理,f(n)就等价于 序列个数为k-1的出栈序列种树*序列个数为n-k的出栈序列种树。即f(n)=f(k-1)*f(n-k)。而k可以从1选到n,再根据加法原理,将k取不同的值,然后求和,得到总序列种数为:f(n)=f(0)f(n-1)+f(1)f(n-2)+……+f(n-1)f(0)。就是卡特兰数的规律,再令f(0)=f(1)=1求解即可。
应用2:括号匹配
【问题描述】
由一对括号,可以组成一种合法序列:()
由两对括号,可以组成两种合法序列:()(),(())
问:由n对括号组成的合法括号序列一共有多少中?
【问题分析】
首先,n对括号我们看成是2n个字符,n个左括号,n个右括号。设问题的解为f(2n)。第0个字符肯定为左括号,而第2*i+1个字符肯定为右括号,如果第2*i个字符为右括号,那么0~2*i一共由2*i+1奇数个字符,而奇数个字符是 无法匹配的。
f(2n)可以转化如下的递推式 f(2n) = f(0)*f(2n-2) + f(2)*f(2n - 4) + ... + f(2n - 4)*f(2) + f(2n-2)*f(0)。f(0)*f(2n-2)表示第0个字符和第1个字符匹配,剩余两部分,一部分0个字符,一部分2n-2个字符。f(2)*f(2n-4)表示 第0个字符和第3个字符匹配,剩余两部分,一部分2个字符,一部分2n-4个字符。以此类推可得出递推式。
f(0)=1,分别计算出f(1),f(2),f(3),f(4),f(5),得出f(2n)就是一个卡特兰数的数列。
应用3:二叉树生成问题
【问题描述】
n个节点 构成的二叉数,共有多少情形?
【问题分析】
设题解为f(n),T(i,j)表示:一颗二叉树,它的左子树有i个节点,右子树有j个节点。
根肯定会占用一个节点,那么它的左右子树:T(0,n-1),T(1,n-2),T(2,n-3),...,T(n-1,0)。
那么f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*f(n-3)+...+f(n-1)*f(0)。假设 f(0)=1,那么f(1)=1,f(2)=2,f(3)=5,满足卡特兰数的规律。
应用4:矩阵链乘
【问题描述】
矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?
【问题分析】
首先通过括号化,将P分成两个部分,然后分别对两个部分进行括号化。比如分成(a1)×(a2×a3.....×an),然后再对(a1)和(a2×a3.....×an)分别括号化;又如分成(a1×a2)×(a3.....×an),然后再对(a1×a2)和(a3.....×an)括号化。
设n个矩阵的括号化方案的种数为f(n),那么问题的解为f(n) = f(1)*f(n-1) + f(2)*f(n-2) + f(3)*f(n-3) + f(n-1)*f(1)。f(1)*f(n-1)表示分成(a1)×(a2×a3.....×an)两部分,然后分别括号化。
计算开始几项,f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 5。结合递归式,满足卡特兰数规律。
相关文章:
卡特兰数学习
1,概念 卡特兰数(英语:Catalan number),又称卡塔兰数,明安图数。是组合数学中一种常出现于各种计数问题中的数列。它在不同的计数问题中频繁出现。 2,公式 卡特兰数的递推公式为:f(…...
第05章 10 地形梯度场模拟显示
在 VTK(Visualization Toolkit)中,可以通过计算地形数据的梯度场,并用箭头或线条来表示梯度方向和大小,从而模拟显示地形梯度场。以下是一个示例代码,展示了如何使用 VTK 和 C 来计算和显示地形数据的梯度场…...
2023CISCN初赛unzip
2023CISCN初赛unzip 随便上传一个文件,会自动跳转到uplaod.php目录下,源码如下: <?php error_reporting(0); highlight_file(__FILE__);$finfo finfo_open(FILEINFO_MIME_TYPE); if (finfo_file($finfo, $_FILES["file"]["tmp_name…...
计算机网络 (55)流失存储音频/视频
一、定义与特点 定义:流式存储音频/视频是指经过压缩并存储在服务器上的多媒体文件,客户端可以通过互联网边下载边播放这些文件,也称为音频/视频点播。 特点: 边下载边播放:用户无需等待整个文件下载完成即可开始播放…...
Linux通过docker部署京东矩阵容器服务
获取激活码 将京东无线宝app升级到最新版,然后打开首页,点击号 选择添加容器矩阵,然后获取激活码 运行容器 read -p "请输入你的激活码: " ACTIVECODE;read -p "请输入宿主机的缓存路径: " src;docker rm -f cmatrix;docker run -d -it --name cmatrix …...
【MySQL】悲观锁和乐观锁的原理和应用场景
悲观锁和乐观锁,并不是 MySQL 或者数据库中独有的概念,而是并发编程的基本概念。 主要区别在于,操作共享数据时,“悲观锁”认为数据出现冲突的可能性更大,而“乐观锁”则是认为大部分情况不会出现冲突,进而…...
Java Web-Tomcat Servlet
Web服务器-Tomcat Web服务器简介 Web 服务器是一种软件程序,它主要用于在网络上接收和处理客户端(如浏览器)发送的 HTTP 请求,并返回相应的网页内容或数据。以下是关于 Web 服务器的详细介绍: 功能 接收请求&#…...
老牌工具被破!
屏幕录制技术因其高效的信息传递能力在多个行业中得到了广泛应用,在教育领域,教师利用屏幕录制制作在线课程。在企业培训中,它为新员工提供了灵活的学习方式。在直播、游戏时,录制分享精彩内容。在客户支持中,客服人员…...
在计算机上本地运行 Deepseek R1
Download Ollama on Linux Download Ollama on Windows Download Ollama on macOS Deepseek R1 是一个强大的人工智能模型,在科技界掀起了波澜。它是一个开源语言模型,可以与 GPT-4 等大玩家展开竞争。但更重要的是,与其他一些模型不同&…...
MongoDB中常用的几种高可用技术方案及优缺点
MongoDB 的高可用性方案主要依赖于其内置的 副本集 (Replica Set) 和 Sharding 机制。下面是一些常见的高可用性技术方案: 1. 副本集 (Replica Set) 副本集是 MongoDB 提供的主要高可用性解决方案,确保数据在多个节点之间的冗余存储和自动故障恢复。副…...
【GoLang】利用validator包实现服务端参数校验时自定义错误信息
在C/S架构下,服务端在校验请求参数时,若出现参数错误,要响应给客户端一个错误消息,通常我们会统一响应“参数错误”。 但是,如果只是一味的提示参数错误,我并不知道具体是哪个参数错了呀!能不能…...
异或哈希总结
例题 例题1https://codeforces.com/problemset/problem/1175/Fhttps://codeforces.com/problemset/problem/1175/F 例题2https://codeforces.com/contest/2014/problem/Hhttps://codeforces.com/contest/2014/problem/H例题4https://codeforces.com/contest/1418/problem/Ght…...
【Rust自学】15.7. 循环引用导致内存泄漏
说句题外话,这篇文章真心很难,有看不懂可以在评论区问,我会尽快作答的。 喜欢的话别忘了点赞、收藏加关注哦(加关注即可阅读全文),对接下来的教程有兴趣的可以关注专栏。谢谢喵!(・ω…...
C#AWS signatureV4对接Amazon接口
马上要放假了,需要抓紧时间测试对接一个三方接口,对方是使用Amazon服务的,国内不多见,能查的资(代)料(码),时间紧比较紧,也没有时间去啃Amazon的文档,主要我的英文水平也不行,于是粗…...
C语言操作符(下)
上一篇文章传送门:操作符上 前言:上期我们介绍了C语言的操作符的使用方法,这期我们主要侧重讲当我们已经了解了操作符的基本知识后怎样样来看待运算路径的问题。 操作符 一,优先级和结合性1,优先级2,结合性…...
学习资料收藏 游戏开发
本文整理了本人在学习 Unity3D 游戏开发过程中知晓的一些学习资料。 视频教程 siki学院 M_Studio Unity中文课堂 博客 林新发 浅墨_毛星云 冯乐乐 Roystan Sorumi 宣雨松 陆泽西 书籍 《Unity 游戏设计与实现》(加藤政树) 《Unity Shader 入…...
我的2024年总结
趁着摸鱼赶紧写一下吧 去年目标review 还是将去年的目标完成了一些 【接纳不完美,多拍照片】 这个还是部分做到了,今年和一些朋友们见面时都注意拍照留记录了,不过还可以继续加强,因为外貌上发生了重大变化,下面细说…...
freeswitch在centos上编译过程
操作系统:centos9-last usr/local/freeswitch/bin/freeswitch -version FreeSWITCH version: 1.10.13-devgit~20250125T131725Z~3f1e4bf90a~64bit (git 3f1e4bf 2025-01-25 13:17:25Z 64bit)vi /etc/ssh/sshd_config ip a nmtui reboot ip a curl -o /etc/pki/rpm-…...
docker如何查看容器启动命令(已运行的容器)
docker ps 查看正在运行的容器 该命令主要是为了详细展示查看运行时的command参数 # 通过docker --no-trunc参数来详细展示容器运行命令 docker ps -a --no-trunc | grep <container_name>通过docker inspect命令 使用docker inspect,但是docker inspect打…...
正则表达式以及Qt中的使用
目录 一、正则表达式 1、基本匹配: 2、元字符: 2.1 .运算符: 2.2 字符集: 2.3 重复次数: 2.4 量词{} 2.5 特征标群() 2.6 或运算符 2.7 \反斜线转码特殊字符 2.8 锚点 3、简写字符 4、零宽度断言 4.1 正…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
