数据结构的一道题

时间:2022-09-29 19:06:20

偶然看到的一个小题,差点被忽略了,题目大概是这样的:
a,b,c,三个元素依次入栈,问有多少种出栈顺序?
意思是入栈的顺序必须是a,b,c,我是这样想的,分三种情况,
1:a先出栈,即a入栈后就出栈,然后可以b入栈,出栈,c入栈,出栈,
那么出栈顺序就是a,b,c;
或者b入栈,c入栈,c出栈,b出栈,顺序为a,c,b
2:b先出栈,出栈顺序可以是b,c,a和b,a,c
3:c先出栈,由于入栈必须是a,b,c,所以出栈只能是c,b,a
所以这类题中三个元素有5种出栈顺序
如果把问题延伸呢?4个呢?5个呢?n个呢?
我搜了下,有些人真是高智商,https://en.wikipedia.org/wiki/Catalan_number这是他的详细解答

假设n个元素依次进栈,出栈的顺序有f(n)中,很容易得到:
f(1)=1;
f(2)=2;
f(3)=5;
为了方便,设f(0)=1;
结论就是:
f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*f(n-3)+……+f(n-1)*f(0);
那么这么算就很简单了(为什么这么做我就不去探究了,也探究不出来,哪位有兴趣可以自己去试试),f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0)=5+2+2+5=14