区块链技术博客
www.b2bchain.cn

卡特兰数那些事–通过一道数据结构题来看卡特兰数的讲解

这篇文章主要介绍了卡特兰数那些事–通过一道数据结构题来看卡特兰数的讲解,通过具体代码讲解8412并且分析了卡特兰数那些事–通过一道数据结构题来看卡特兰数的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了卡特兰数那些事–通过一道数据结构题来看卡特兰数的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=8412。具体如下:

卡特兰数那些事–通过一道数据结构题来看卡特兰数

1. 什么是卡特兰数

对于卡特兰数h(n)
有递推关系:h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)*h(0) (n>=2)
递推关系的解为:h(n)=C(2n,n)/(n+1) (n=0,1,2,…)

递推关系的另类解为:h(n)=C(2n,n) – C(2n,n-1) (n=0,1,2,…)
(来自百度百科)


2. 有关卡特兰数的一个问题

首先,我们可以看一看这个问题:

我们有一个操作数序列,1,2,…,n
现在可以进行两种操作:

  1. 将一个数,从操作数序列的头端移到栈的头端
  2. 将一个数,从栈的头端移到输出序列的尾端
    使用这两种操作,由一个操作数序列就可以得到一系列的输出序列.
    求由操作数序列 1,2,…,n 经过操作可能得到的输出序列的总数。
    –(来自洛谷)

一言以蔽之,就是求“当一个栈(无穷大)的进栈序列为1,2,3,…,n时,有多少个不同的出栈序列?”


3. 这个问题和卡特兰数有什么关系?

首先,我们设 f(n)=序列个数为n的出栈序列种数。(我们假定,最后出栈的元素为k,显然,k取不同值时的情况是相互独立的,也就是求出每种k最后出栈的情况数后可用加法原则,由于k最后出栈,因此,在k入栈之前,比k小的值均出栈,此处情况有f(k-1)种,而之后比k大的值入栈,且都在k之前出栈,因此有f(n-k)种方式,由于比k小和比k大的值入栈出栈情况是相互独立的,此处可用乘法原则,f(n-k)*f(k-1)种,求和便是卡特兰递归式。
(百度百科)


4. 问题的解法

如何考虑这个问题呢?我们先将问题简化。

这个问题和“我有一个箱子A,里面装了n个一模一样的小球。现在我要将它们从箱子A移到箱子B,最后移到箱子C,每个小球都要进箱子一次,问有多少种取法”等价。

那有同学就会问了。“诶,n个一模一样的小球怎么模拟1,2,3,…,n这n个不同的数呢?”

原因就在于我们只关注“放入小球”和“取出小球”这两个动作上。如果我们将“放入小球”视作为原题中的“将序列头端元素移到栈顶”,“取出小球”视作为原题中的“取出栈顶元素”(因为小球都是相同的,不妨这么看),这两个问题就是等价的。

很容易发现,这个问题的关键在于箱子B,也就是栈中的小球/元素数量必须大于等于0。
为了描述这个问题,我们考虑一个2n位的2进制数。(首位可以为0)

从首位开始写,将小球放入B记为1,取出记为0。 那么【栈中的小球/元素数量必须大于等于0】就意味着从左开始一位一位看,看过的1的数量始终【大于等于】看过的0的数量。

我们只要用【所有2n位的二进制数个数】 – 【不符合条件的2n位二进制数个数】 就能得到答案

首先,【所有2n位的二进制数个数】=C(2n,n)
可以解释为2n个位置里挑n个位置是1

【不符合条件的2n位二进制数个数】怎么求呢?

【不符合条件的2n位二进制数】是什么意思?就是指,从左开始数,存在某个位置,左边所有1的数量【小于】左边所有0的数量。我们定位到第一次出现这种情况的地方,那这个地方必然为0。我们如果假设左边有k个1,那么0就有k+1个。
右边就有n-k个1,n-k-1个0.

接下来,我们把右边的0和1互换。将0变为1,1变为0。那么右边就有n-k个0,n-k-1个1. 因为左边有k个1,那么0就有k+1个,所以这个二进制数中,0共有n+1个,1共有n-1个。

这种【0共有n+1个,1共有n-1个】的二进制数和【不符合条件的2n位二进制数】一一对应。我们求【0共有n+1个,1共有n-1个】的二进制数个数就好。

答案很显然是C(2n,n+1) (或者C(2n,n-1))

综上,这样的二进制数共有 C(2n,n) – C(2n,n-1) (n=0,1,2,…) 个。

所以,问题“当一个栈(无穷大)的进栈序列为1,2,3,…,n时,有多少个不同的出栈序列?”的答案就被我们求得了。


5. 总结

这个问题的答案其实就是卡特兰数,上面的做法也是对卡特兰数递推公式的一种证明。

本文地址https://www.b2bchain.cn/?p=8412

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 卡特兰数那些事–通过一道数据结构题来看卡特兰数的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们