试证明：若借助栈由输入序列12…n得到的输出序列为p1p2…

[问答题]

试证明：若借助栈由输入序列12…n得到的输出序列为p₁p₂…pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k使p_j<p_k<p_i。

推荐

赞花婆

这个问题和3.1题比较相似。因为输入序列是从小到大排列的，所以若p_j<p_k<p_i，则可以理解为通过输入序列p_jp_kp_i可以得到输出序列p_ip_jp_k，显然通过序列123是无法得到312的，参见3.1题。所以不可能存在着i<j<k使p_j<p_k<p_i。

发表于 2018-05-05 22:30:28 回复(0)

jsword

利用反证法。

假设存在i<j<k使pj<pk<pi，那么各元素进栈出栈后的顺序为pj,pk,pi.具体分析：

1)当 i < j 时，pj < pi ,说明pj是在pi进栈后进栈，且pj在pi前面出栈

2)当 j < k时，pj < pk,说明pj必须在pk入栈前就出栈，否则pj就被压在pk下面了。

3)当i < k时，pk < pi，表明pi是先于pk进栈。

这与正确的出栈顺序pi,pj,pk矛盾

发表于 2019-05-01 16:00:06 回复(1)

水坎火离

标记一下，《TAOCP》的2.2.1中练习的第5题

发表于 2020-02-25 12:12:50 回复(0)

提交观点

问题信息

上传者：赞花婆

难度：

3条回答 3收藏 5961浏览

扫一扫，把题目装进口袋