若借助栈由输入序列12...n得到的输出序列为p1p2...pn,则证在输出序列中不会出现：存在i<j<k使pj<pk<pi

答案:3 悬赏:70 手机版

解决时间 2021-01-28 00:25

提问者网友：感性作祟
2021-01-27 01:34

试证明：若借助栈由输入序列12...n得到的输出序列为p1p2...pn（它是输入序列的一个排列）,则在输出序列中不会出现：存在i<j<k使pj<pk<pi

最佳答案

五星知识达人网友：拾荒鲤
2021-01-27 02:27

这题可以用反证法证明：
假设存在i<j<k,且也满足pj<pk<pi,对于i<j<k,可看出i先进栈，然后j，最后k；而对于pj<pk<pi,则可看出pi中i在j和k之后进栈（因为pi先出栈），与前者i先进栈相矛盾（栈是先进后出的，而这个造成了先进先出），所以假设不对，所以不会出现存在i<j<k使pj<pk<pi；

希望对你有帮助,谢谢！

全部回答

1楼网友：三千妖杀
2021-01-27 03:35

我怎么没看出

2楼网友：像个废品
2021-01-27 03:22

你说呢...

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息