本文主要是介绍N个元素进栈 出栈情况种数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1.逐一求解
- 2.卡特兰数的引入
- 3.得出结论
1.逐一求解
面对此类问题 我们无法直接分析元素个数 为N的情况 通常我们都会逐一分析
设定一个函数 f(N):N为元素个数 f(N)为出栈顺序种数
显然:
f(1) = 1:af(2) = 2:a,b b,af(3) = 5:a,b,c a,c,b b,a,c b,c,a /*c,a,b*/ c,b,af(4) = ?
当N为4时 问题趋于复杂 那么怎么解决呢?
我们从小就开始学数学 小学数学有一章是–找规律
很明显 这种问题就是找规律的
只不过有些规律难找 我们一一研究
接下来我会以新口吻来分析这个问题 各位一看便知
假定f(0) = 1f(1) = 1:a
a第1个出栈 前面有0个出栈 后面有0个出栈 f(0) * f(0) = 1 f(1) = 1f(2) = 2:a,b b,a
a第1个出栈 前面有0个出栈 后面有1个出栈 f(0) * f(1) = 1
a第2个出栈 前面有1个出栈 后面有0个出栈 f(1) * f(0) = 1 f(2) = 2f(3) = 5:a,b,c a,c,b b,a,c b,c,a /*c,a,b*/ c,b,a
a第1个出栈 前面有0个出栈 后面有2个出栈 f(0) * f(2) = 2
a第2个出栈 前面有1个出栈 后面有1个出栈 f(1) * f(1) = 1
a第3个出栈 前面有2个出栈 后面有0个出栈 f(2) * f(0) = 2 f(3) = 5f(4) = ?
类似于递归思想 将难解的大问题转换为易于求解的子问题 一一求解
那么f(4)是多少呢? 这时就很容易解决了
A第1个出栈,前面有0个出栈 后面有3个出栈 f(0) * f(3) = 5
A第2个出栈,前面有1个出栈 后面有2个出栈 f(1) * f(2) = 2
A第3个出栈,前面有2个出栈 后面有1个出栈 f(2) * f(1) = 2
A第4个出栈,前面有3个出栈 后面有0个出栈 f(3) * f(0) = 5 f(4) = 14
递推:
f(n) = f(0)f(n-1) + f(1)f(n-2) + .....+ f(n-1)f(0)
2.卡特兰数的引入
那么这个数等于多少呢?实际上 早有先人研究过这一类数学问题 这个数就是著名的卡特兰数
以下内容来源于百度卡特兰数
3.得出结论
n个元素进栈,出栈情况种数为
这篇关于N个元素进栈 出栈情况种数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!