一类连线问题中栈和Catalan数的应用

2023-12-03 22:18

本文主要是介绍一类连线问题中栈和Catalan数的应用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

《数据结构》课程中有个经典的栈应用的例题:开关盒布线问题。这个题用栈来解决是非常奇妙的,题目是说给定一种布线情况,判断是否出现了短路,短路的定义就是开关盒表面的排线不能出现交叉。思路是顺(逆)时针遍历,遇到起点时入栈,遇到终点时,则将当前栈顶元素出栈,这样到最后若栈空,则布局合法,否则会出现短路。为什么呢?因为任一条线将开关盒表面分成了两个区域,不短路的情况是这两个区域不能出现一个区域包括某条线的起点而终点却分布在另一个区域。另外,布线其实是无向的,故为了便于顺(逆)时针遍历,应将输入的布线对略作调整,保证起点大(小)于终点。
这个问题涉及到了出栈入栈的问题,且保证最后栈空。那么稍稍引出本文的主题,Catalan数列的应用,应用有很多,今天着重讲的是连线问题的应用:给一个n个顶点的多边形,问两个顶点相连,最后没有孤立点且不交叉共有多少种连法(是不是神似开关盒布线)?
这个解就是Catalan数列,且记为cata[n].为什么呢,先看看Catalan数列的另一个经典应用:一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列? 想必对Catalan数列有所了解的人都见过这个例子,也都知道用Catalan解决,至于为什么网上有详细解释,请自行摆渡。
那个连线问题其实是综合了开关盒布线和出入栈了的,就是相当于尝试所有的布线对组合,看有多少种合法的状态。具体讲就是假设n个顶点,编号1到n,对每个点均有两种可能的角色,要么是起点要么是终点,那么起点代表入栈,用1表示,终点代表出栈,用0表示,那么就是一连串的01字串了,跟那个栈应用就联系起来了,不同于开关盒布线之处是:由于算法本质是不一样的,跟开关盒布线的代码是不一样的,只是思想有一点相似之处。本题保证最后的结果不会有元素留在栈中,而判断过程就是判断是否有非法出栈操作:从空栈中pop。
最后给个代码实现:求cata[n]

最后说下以前的一篇日志《pz伯伯的番茄排序》,也是Catalan数列解决的,那个题目也相当于将2n个番茄编号,前n(1-->n)个代表前n个最小的,用01……n表示;后n(n+1-->2n)个代表后n个次小的,用1(n+1)……2n表示。

那么含有6个0,6个1的序列,就对应一种方案.
比如000000111111就对应着 //注意每个0是不一样的,1也是不一样的
第一排:0 1 2 3 4 5
第二排:6 7 8 9 10 11
010101010101就对应着
第一排:0 2 4 6 8 10
第二排:1 3 5 7 9 11
问题转换为,这样的满足条件的01序列有多少个.
观察1的出现,我们考虑这一个出现能不能放在第二排,显然,在这个1之前出现的那些0,1对应的人要么是在这个1左边,要么是在这个1前面.而肯定要有一个0的,在这个1前面,统计在这个1之前的0和1的个数. 也就是要求,0的个数大于1的个数.
也就是Catalan数列的应用

这篇关于一类连线问题中栈和Catalan数的应用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/451065

相关文章

VSCode中C/C++编码乱码问题的两种解决方法

《VSCode中C/C++编码乱码问题的两种解决方法》在中国地区,Windows系统中的cmd和PowerShell默认编码是GBK,但VSCode默认使用UTF-8编码,这种编码不一致会导致在VSC... 目录问题方法一:通过 Code Runner 插件调整编码配置步骤方法二:在 PowerShell

mybatis-plus分页无效问题解决

《mybatis-plus分页无效问题解决》本文主要介绍了mybatis-plus分页无效问题解决,原因是配置分页插件的版本问题,旧版本和新版本的MyBatis-Plus需要不同的分页配置,感兴趣的可... 昨天在做一www.chinasem.cn个新项目使用myBATis-plus分页一直失败,后来经过多方

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Spring MVC跨域问题及解决

《SpringMVC跨域问题及解决》:本文主要介绍SpringMVC跨域问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录跨域问题不同的域同源策略解决方法1.CORS2.jsONP3.局部解决方案4.全局解决方法总结跨域问题不同的域协议、域名、端口

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

Spring AI集成DeepSeek三步搞定Java智能应用的详细过程

《SpringAI集成DeepSeek三步搞定Java智能应用的详细过程》本文介绍了如何使用SpringAI集成DeepSeek,一个国内顶尖的多模态大模型,SpringAI提供了一套统一的接口,简... 目录DeepSeek 介绍Spring AI 是什么?Spring AI 的主要功能包括1、环境准备2