一,问题:n个拿着1元,n个人拿着2元去买票。票价一元,且售票元只能用n个人购票的一元给2元的找零。问有几种排列方法
分析:卡特兰数方法
递推公式:F(2*n) =F(0)*F(2(n-1)) +F(1)*F(2(n-2))+……+F(2(n-1))*F(0)
F(n) =F(0)*F(n-1) +F(1)*F(n-2)+……+F(n-1)*F(0)
解答:
所有序列的个数 :C (2n,n) (ps:由于数学函数难打,这里表示从2n个位置中挑选n个存放1)
非法序列的个数:假设有一种序列 n-1个1元,n+1个2元。这种序列个数:C (2n,n-1)
存在K使得这个序列中1的个数比2少1个,则将其后的所有1换成2,所有2换成1。则该序列有n个1,n个2。这样这种序列(n-1个1,n+1个2)跟(n个1,n个2)一一对应。所以,非法序列个数为:C (2n,n-1)
所以合法序列个数:C (2n,n) - C (2n,n-1) =C (2n,n) /(n+1)
二,扩展问题:n个结点可以构造多少个不同的二叉树
分析解答:
当n=1时,只有1个根节点,则只能组成1种形态的二叉树,令n个节点可组成的二叉树数量表示为h(n),则h(1)=1; h(0)=0;
当n=2时,1个根节点固定,还有2-1个节点。这一个节点可以分成(1,0),(0,1)两组。即左边放1个,右边放0个;或者左边放0个,右边放1个。即:h(2)=h(0)*h(1)+h(1)*h(0)=2,则能组成2种形态的二叉树。
当n=3时,1个根节点固定,还有2个节点。这2个节点可以分成(2,0),(1,1),(0,2)3组。即h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5,则能组成5种形态的二叉树。
以此类推,当n>=2时,可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种,即符合Catalan数的定义,可直接利用通项公式得出结果。
令h(1)=1,h(0)=1,catalan数(卡特兰数)满足递归式:
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)
另类递归式:
h(n)=((4*n-2)/(n+1))*h(n-1);
该递推关系的解为:
h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
扩展:
卡特兰数的应用 (实质上都是递归等式的应用)
1、括号化问题 矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(h(n)种)
2、出栈次序问题 一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?
分析
对于每一个数来说,必须进栈一次、出栈一次。我们把进栈设为状态‘1’,出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。
在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所求。
不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。
反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。
因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。
显然,不符合要求的方案数为c(2n,n+1)。由此得出 输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。
(这个公式的下标是从h(0)=1开始的)
类似问题
有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)
3、凸多边形的三角剖分问题 求将一个凸多边形区域分成三角形区域的方法数。
类似:一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?
类似:在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
分享到:
相关推荐
11085 买票找零 时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0 题型: 编程题 语言: 无限制 Description 一场激烈足球赛即将开始,售票员紧张地卖票着……。 每张球票50元,现在有2n(1)个球迷排队...
一场激烈足球赛即将开始,售票员紧张地卖票着……。 每张球票50元,现在有2n(1)个球迷排队购票,其中n个...假设开始售票时售票处没有零钱可以找零。 问这2n个人有多少种排队方式,不至使售票处出现找不出零的局面?
买票找零算法解析.pptx
多线程买票是java中的一个经典案例,其主要思想无非包括2点,synchronized和锁,两者中,前者实现同步,后者为同步的线程提供锁,从而实现多个线程共享同一份资源时候,能够同步进行; 经典的方式是synchronized + 锁...
火车站买票问题代码
模拟三个人排队买票,张某、李某、赵某买电影票、售票员只有3张5元的钱, 电影票5元钱一张。张某拿20元一张的新人民币排在李的钱买票, 李某排在赵的前面拿一张10元的人民币买票,赵某拿一张5元的人民币买票 ...
三年级下册数学买票问题PPT,三年级下册数学买票问题
上课写的一个多线程买票系统,还不是很完美,希望大神指点。
模拟多人不同面值购票找零的多线程代码(java版)模拟多人不同面值购票找零的多线程代码(java版)
设计一个程序模拟插队买票的过程,本实验假设售票大厅有2个售票窗口,无论到哪个窗口买票都必须排队,但是新来的人不一定排在队尾,允许插队(即直接排在朋友的后面)。假设已经在排队的人不会离开,也不会移到其他...
编程建立循环队列存储结构,对排队买票过程进行模拟。要求程序在控制台屏幕上显示字符菜单: 1. 排队——输入新到达的买票人姓名,加入买票队列中; 2. 售票——排队队列中最前面的人购票成功,显示信息并将其从队列...
数据结构课程设计 两江大学出版社 插队买票
自己用C语言做的程序,实现排队买票的模拟,运行结果没问题,代码有些长~
车票无忧,快速买票软件,可以准时抢火车票。
用c++实现动态规划求歌迷排队买票,直接运行,很好的
抢票软件,春节买票必备,绝对安全的抢票软件有教程
影院售票系统,模仿现实生活中的售票,可以买不同种类 的票。
电影院买票小项目可以实现售票选座查看当前场次售出的票的功能
linux多线程使用实例:在linux系统环境下的买票退票系统
问题描述:排队买票每个队伍允许插队。每次一个人入队列,如果这个入队的人发现队伍中有自己的朋友,则可以插入到这个朋友的后面;当队伍中朋友不止一个的时候,这个人要排在最后一个朋友的后面;如果队伍中没有朋友...