一道关于递归的题目,麻烦解释下算法.
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/08/24 21:16:15
一道关于递归的题目,麻烦解释下算法.
1、出栈问题.有两个栈,S1和S2,其中S1中有按1、2…n顺 序的n个不同的元素,S2为空.现在可以做这样两种操作:(1) 从S1中取出一个元素放入S2中;(2)将S2最顶端元素弹出(弹 出元素不再参与下面的操作).直到所有元素都被弹出为 止,问不同的弹出顺序有多少种?
1、出栈问题.有两个栈,S1和S2,其中S1中有按1、2…n顺 序的n个不同的元素,S2为空.现在可以做这样两种操作:(1) 从S1中取出一个元素放入S2中;(2)将S2最顶端元素弹出(弹 出元素不再参与下面的操作).直到所有元素都被弹出为 止,问不同的弹出顺序有多少种?
栈是后进先出的.先从一个具体一些的例子来看吧,比如S1中有A、B、C、D,第一种情况是每次从S1中取出一个元素后,接下来就弹出.即从S1中取出A放入S2中,然后弹出,然后取出B,弹出;然后是C,最后是D,这样顺序为ABCD.第二种是取出C放入S2后再取出D,这时S2的最顶端元素是D,即先弹出D,这样顺序为ABDC.第三种,取出B放入S2后,取出C再取出D,弹出ADCB.第四种,DCBA.第五种,CBAD.第六种,BADC.第七种,BACD.应该就有这些了吧,如果是n个元素,那应该多看几个元素找规律吧,公式还没推出来