12个高矮不同的人,排队问题。引出卡特兰数(Catalan)

12个高矮不同的人,排队问题。引出卡特兰数(Catalan)。

      • 等价问题1
      • 等价问题2
      • 【解法】

传闻是【阿里巴巴笔试题】:12 个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

网上看了很多解答,但理解起来仍然费劲。索性自己动手,加强记忆。
本文用2次 “等价证明” 将答案引到卡特兰数。不正之处,欢迎指出。

等价问题1

由6个0和6个1组成一个12位的二进制数,要求从左到右扫描,任意位置,0的累计数都不小于1的累计数,求满足条件的组合有多少种。

【证明】:把12个人以A,B,C…F,L从低到高标记。将第一排位置标上0,第二排位置标上1。如下图:
选位置
然后从A-L顺序开始分配位置。根据分配顺序,得出一个由6个0和6个1组成的二进制数。又因为每次分配的都是当前最矮的人,所以分配必须遵循如下规则,才能满足题目要求。
1:无论分配0还是1,只能分配左边数过来第一个没人的位置。
2:当想分配1的时候,对应的0上必须有人。
根据以上两点,得出这个这个12位的数在任意时刻,0的累计数都不小于1的累计数。证明完毕。

等价问题2

有6个元素和一个栈,任何一个元素进栈后可选择立即出栈 or 栈里不动,比如第一个元素进栈完毕,下一个动作可以选择出栈或让后一个元素进栈,进栈次序为1、2、3、4、5、6,问不同的出栈次序有几种?

6个元素对应6个【进栈动作】和6和【出栈动作】,总计12个动作。
由【等价问题1】我们得出了一个由6个0和6个1组成的12位的二进制数,并且任意位置的0的累计数都不小于1的累计数。例如:010101010101、000111000111。
我们把0看成元素入栈,1看成元素出栈。因为栈内必须有元素才能选择【出栈动作】,所以0的累计数【入栈动作】在任意时刻都是不小于1【出栈动作】的累计数。得出等价问题1=等价问题2。证明完毕。

【解法】

基于【等价问题2】,我们假设为n个元素的进出栈操作。定义函数h(n),h(n)为n个元素进出栈次序的解。假设k为最后一个出栈的元素,比k早进栈早出栈的元素有k-1个,那么这k-1个数共有h(k-1)种出栈方式。同理,比K晚进栈早出栈的元素有h-k个,共有h(h-k)种出栈方式。求得当k最后一个出栈时,共有h(k-1)*h(h-k)种出栈方案。因为K是1-n的任意值。得出结果:h(n)=h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)*h(0)。
当只有一个元素时,即n=1时,只有一种出栈方式,得出:h(1)=1。又根据公式h(1)=h(0)*h(0),得出h(0)=1。即h(1)=1,h(0)=1。

java代码实现h(n);将n = 6带入,计算出结果132。

    public static int h(int n){
        if(n == 0 || n == 1){
            return 1;
        }
        int r = 0;
        for (int i = 0; i < n; i++){
            r += h(i) * h(n - i -1);
        }
        return r;
    }

参考:
https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746
https://blog.csdn.net/qq_38216239/article/details/78738785

热门文章

暂无图片
编程学习 ·

web照片存储网站登录后的主页面

web照片存储网站登录后的主页面 在这里插入代码片<%@page import=“java.util.*”%> <%@page import=“com.fh.util.QueryAssistant.QueryAssistant”%> <%@page import=“org.apache.shiro.SecurityUtils”%> <%@page import=“org.apache.shiro.subject…
暂无图片
编程学习 ·

dexjar用法

将dex文件转换成jar文件: 直接将dex文件拖进d2j-dex2jar.bat 或者 用cmd进行转换将jar文件转换成dex文件: 直接将jar文件拖进d2j-jar2dex.bat 或者 用cmd进行转换
暂无图片
编程学习 ·

Spark1.x升级Spark2.x常见异常Kafka篇【TopicMetadataRequest】

一.原因分析 当Spark从1.x升级到2.x时,如果使用SparkStreaming加载Kafka的数据,即使Kafka版本没有变化【一般会有所升级】,对应的spark-streaming-kafka也必须升级到对应版本,访问方式也会有所变化。 此处是从Spark1.6.0升级到Spark2.4.3,Kafka略有升级【从2.1.0升级到2.2…
暂无图片
编程学习 ·

抖音上卖什么最热销?抖音上最热销的产品是什么?

抖音带货卖什么类型产品热门,抖音带货做哪个领域好自去年六月第一批100个内测账号入驻以来,抖音购物车至今已运营一年有余。随着这一年来功能打磨、生态打通等不断完善,抖音购物车已成为KOL带货变现的绝佳途径之一。第一种,在抖音里卖减肥产品。现在的人生活条件都比较好,…
暂无图片
中恒嘉业 ·

关于主从复制的超详细解析(全)

目录前言1. 主从复制1.1 方式2. Mysql的主从复制2.1 一主一从2.1.1 window和linux通讯2.1.2 linux和linux的通讯2.2 双主双从3. Redis的主从复制3.1 哨兵模式3.2 java代码结合前言 主要介绍mysql的主从复制以及redis的主从复制 能由浅入深的明白原理以及如何操作 再者&#xf…
暂无图片
郑州普通话 ·

android音视频何俊林,最新大厂Android社招面试经验汇总

实习生: 对于实习生而言的话,可能对于android方面的要求并不是特别的高,比较注重基础,但是基本的得会,比如: 1.四大组件基本的概念以及使用。2.activity的生命周期流程,这是最基本的,但是你得清楚到底是啥时候调用各个方法,如一个页面(A)当前正在跟用户交互,弹出一个…
暂无图片
郑州普通话 ·

scratch质数判断器 电子学会图形化编程scratch等级考试四级真题和答案解析2021-12

scratch质数判断器 一、题目要求 质数又叫素数,是在大于1的自然数中,除1和其本身以外没有其他因数的自然是,请设计一个质数判断器 1、准备工作 保留小猫角色,白色背景 2、功能实现 通过询问并等待输入一个大于1的自然数 判断输入的数是否是质数,并说出判断结果 二、案例…
暂无图片
代理记账 ·

在web应用中发送和接收Jakarta消息

Running the websimplemessage Example To Package and Deploy websimplemessage Using Maven _1、Make sure that GlassFish Server has been started (see Starting and Stopping GlassFish Server). _2、In a terminal window, go to: tut-install/examples/jms/websimp…
暂无图片
cgfy ·

C++学习日记2——函数、封装、对象特性

一、函数 1.1 函数默认参数 1.1.1 简介 在C中&#xff0c;函数的形参列表中的形参是可以有默认值的 1.1.2 语法 返回值类型 函数名 (参数 默认值) {} 1.1.3 代码 #include <iostream> using namespace std;// 函数的默认参数 int func(int a, int b 20, int c 30…
暂无图片
coreui ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
coreui ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
未来博客 ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
未来博客 ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
建站日记 ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
建站日记 ·

NLP聊天机器人原理(seq2seq模型)

一、seq2seq模型 1.概念 seq2seq是一个Encoder-Decoder结构的网络&#xff0c;它的输入是一个序列&#xff0c;输出也是一个序列。Encoder中将一个可变长度的信号序列变为固定长度的向量表达&#xff0c;Decoder将这个固定长度的向量变成可变长度的目标的信号序列。这个结构最…
暂无图片
mfbz ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
mfbz ·

全渠道会员通-天猫会员通3: 会员运营内容准备

在天猫会员通技术对接开发过程中&#xff0c;为了通知存量会员的通知工作&#xff0c;发挥会员通的优势&#xff0c;品牌需要做好以下事宜&#xff1a; 会员体系暂停公告&#xff1a;因会员通技术升级期间&#xff0c;会员服务将被暂停&#xff0c;店铺tab中会员入口将被下线&…
暂无图片
珊珊日记 ·

C# 执行Javascript脚本

c#教程https://www.xin3721.com/eschool/CSharpxin3721/ 前一阵子使用C#编写SCXML状态机&#xff0c;需要解析EMCScript表达式&#xff0c;使用了Jint库&#xff08;https://github.com/sebastienros/jint/)&#xff0c;当时感觉与C#之间的数据转换不是很方便。这两天有时间又关…
暂无图片
珊珊日记 ·

第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛

A.大学期末现状 题目描述 作为一名大学生的你&#xff0c;现在又到了期末查成绩的时候&#xff0c;当你的成绩大于等于60时请输出“jige,haoye!”,否则输出"laoshi,caicai,laolao"。 输入描述: 一行&#xff0c;一个整数x代表你的成绩&#xff08;0<x<100&a…