手机版 | 登陆 | 注册 | 留言 | 设首页 | 加收藏
当前位置: 网站首页 > 精彩文章 > 文章 当前位置: 精彩文章 > 文章

NOIP2018初赛复习之栈类问题与卡特兰数

时间:2018-10-03    点击: 次    来源:网络    作者:佚名 - 小 + 大

栈相信大家都了解我就不用说了吧,但是这个卡特兰数东西我是真的不熟悉。

首先对于NOIP初赛肯定会考有关栈的东西,关于栈无非是两种题型:1.模拟判断出入栈的顺序 2.求出栈顺序有多少种(用catalan带入计算即可,上面的图片说的算是挺清楚了)

对于计数原理,有些题需要具体分析而不能往卡特兰数上瞎套

但是我看着以下问题还是可以套卡特兰的

1.求出栈顺序

2.求有n个节点的二叉树有多少种形态

其实卡特兰数是由递推关系求通项而由来的,对于某个问题可以满足f(n)=f(n-1)f(0)+f(n-2)f(1)+……….+f(1)f(n-2)+f(0)f(n-1)都可以使用通项公式快速求出

上一篇:关于十进制转任意进制算法的理解

下一篇:关于二叉树中序遍历和后序遍历的理解

备案ICP编号  |   QQ:3558389921  |  地址:山东济南  |  电话:暂不提供  |  
Copyright © 2018 天人文章管理系统 版权所有,授权down1s.com使用 Powered by 55TR.COM