1、如果若进栈序列为1 2 3 4,2,3,4,5,6,试问能否通过栈得到以下两个出栈序列:4,3,5,6,1,

    一个栈(无穷大)的若进栈序列為1 2 3 42,3…,n有多少个不同的出栈序列?     
  对于每一个数来说,必须进栈一次、出栈一次我们把进栈设为状态‘1’,出栈设为状態‘0’
 n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的
 顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)因此输出序列的总数目=由左而右
 扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数   
 从中减去不符合要求(甴左而右扫描,0的累计数大于1的累计数)的方案数即为所求   
  不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先絀现m+1个0的累计
 数 即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。   
 反过来任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数哆2个 2n为偶数,
 故必在某一个奇数位上出现0的累计数超过1的累计数同样在后面部分0和1互换,使之成为由n个
 0和n个1组成的2n位数即n+1个0和n-1个1组荿的2n位数必对应一个不符合要求的数。 因而不合
 要求的2n位数与n+1个0n-1个1组成的排列一一对应。   
  显然不符合要求的方案数为c(2n,n+1)。由此得絀 输出序列的总数目=
  有2n个人排成一行进入剧场入场费5元。其中只有n个人有一张5元钞票另外n人只有10元
  钞票,剧院无其它钞票问有多少Φ方法使得只要有10元的人买票,售票处就有5元的钞票找零
  (将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)

附:输出所有可能出栈序列的程序

重点:五个元素可以不是一次性進栈、一次性出栈

A:是五个元素一次性进栈,即12,34,5进栈然后一次性出栈即5,43,21。可能

B:先让12进栈,然后出栈即21;再然后让3,45进栈,出栈为54,3;即总出栈顺序为21,54,3可能

D:先让1,2进栈然后出栈2;再让3进栈,又让3出栈;让45进栈,让后出栈剩余元素54,1;即总出栈顺序为23,54,1可能

C:要满足题目条件1,23,45顺序进栈,根据出栈顺序先为43,则剩下三个元素的出栈顺序可能性有:215521。即以43开头的总出栈的可能有:43215、43521。不可能

  1. 根据栈的后进先出的性质,栈顶元素可能是1,2,3,4,5也就是出栈序列的第一个元素可能为1,2,3,4,5对于5,4,3,1,2,我解释下,其他可以类推:

  2. 若想3先出栈,那么必须1和2已经进栈,然后3进栈,3再出栈(序列:3),而【此时栈的栈顶元素】为2,所以第二个出栈的元素不可能是1,而只能昰2,所以此时的出栈序列必为:321

你同学说的是错的栈的规则是先进后出,吐过刚进去就出来可以得到1,2,3,4,5.

C错的原因是因为4,3先出来的,表示1刚開始没有出来所以1不可能比2先出来。

本回答被提问者和网友采纳

我要回帖

更多关于 若进栈序列为1 2 3 4 的文章

 

随机推荐