设输入序列为a b c d 试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。【北京科技
序列,两个,北京
已帮助 人
设输入序列为a，b，c，d，试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。【北京科技大学2001一、4(2分)】
请帮忙给出正确答案和分析，谢谢！
-
正确答案：n个元素的排列有n!种但借助栈结构n个入栈元素只可得到1／(n+1)((2n)!／(n!*n!))种出栈序列这个数小于l!。本题4个元素可有14种出栈序列abcd和dcba就是其中两种；有10(41—14=10)种排列得不到其中dabc和adbc是不可能得到的两种。
n个元素的排列有n!种,但借助栈结构,n个入栈元素只可得到1／(n+1)((2n)!／(n!*n!))种出栈序列,这个数小于,l!。本题4个元素,可有14种出栈序列,abcd和dcba就是其中两种；有10(41—14=10)种排列得不到,其中,dabc和adbc是不可能得到的两种。