一个算法题请教....

[yangyaofei]

如下,判断题:

同一组不重复输入序列执行不同的入栈出栈组合操作,所得结果也可能相同

这个是北邮 2005 年的考研题,来源是算法与数据结构 1800 题,答案给的是对的,我搞不明白.出入栈操作组合不应该和序列是一一对应的么?

如果说你认为这道题是书上答案错了,那么下一道题就会让你觉得貌似不是....

同样判断题,同样也是北邮的:

即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作,所得的输出序列也一定相同()

虽然这个题答案是错的,但是估计出题人设计的错误的地方是最后的也一定相同这个地方,说起来就好像改成可能相同就对了一样....而改成可能相同就变成上一题了....

我用数学归纳法也试着证明了一下两个操作组合输出同一个输出序列,证明出两个操作组合相同了,也算出操作组合的数量和输出序列的数量相等了....

当然,我还是觉得有可能是自己错了,所以来这里请教大家...

[shliujing]

标题描述不清，正文描述看着有点累 0 0

[yszx]

上一个：放 5 个取 5 个和放 2 个再放 3 个再取 5 个的结果是一样的

下一个：放 2 取 2 放 3 取 3 和放 3 取 3 放 2 取 2 是不同的

[yangyaofei]

@shliujing 啊,写的比较乱凑合看一下吧.

[yangyaofei]

@yszx 放两个再防三个和放五个有区别??大哥别闹.....

[yszx]

@yangyaofei 当然没区别，但是这两是不同的组合啊

[whwq2012]

@yangyaofei 然后这两个出来，三个再进去啊

[yangyaofei]

@yszx 00001111 和 00 00 1111 是不同的序列? 蛤蛤和蛤 蛤 不是一个蛤?别闹
@whwq2012 黑人问号.jpg

[zhy0216]

以 [1, 3, 5] 为例, s 表示 stack.
操作 1: s.push(1); s.push(3); s.push(5); s.pop(); s.pop();
操作 2: s.push(1); s.push(3); s.pop(); s.push(5); s.pop();

[yszx]

@yangyaofei 是不同的“组合”啊····执行不同的入栈出栈组合操作。出入的序列当然相同，不相同这题答案不就是“错”么。就是不同的入栈出栈组合效果相同的意思啊

[yszx]

@yangyaofei 当然作为程序连在一起是一样的····要么就是我搞错了

[yangyaofei]

@zhy0216 哦~~我明白了!!!谢谢谢谢.思维定式认定非要所有的元素都要进行 push 和 pop 了,茅塞顿开,谢谢谢谢

@yszx 大哥别闹,你那个"组合"并不是题目中说的组合,谢谢.有网友解答我了,同样谢谢你,但是你说的不对.

[yszx]

@yangyaofei [3,5]和[5,3]哎····还是说题目说的是栈里面一样····

[yangyaofei]

@yszx 是输出的序列,比如 12345 你 pu po pu po 之后的序列是 12 说的是 12345 一样 12 一样... pu po pu po 这个不一样.....

[yszx]

@yangyaofei 那么至少 [5 ， 3] 和 [3 ， 5] 是不一样的····

[yszx]

@yangyaofei 好吧···我去搜题目了，然后在别的地方看到这个题目答案是 错。

假如按你这样的条件，绝对不可能相同，因为相同的输出，就要求出栈的位置和顺序完全相同，那么中间填充的入栈也必然相同。
比如说[1,3,5 ， 7]现在要求第一个出栈 5 ，那么只有入栈 1 ，入栈 3 ，入栈 5 这一条路。因为如果不入栈就到不了 5 ，如果继续出栈，则必然会在 5 之前就有出栈。

[yangyaofei]

@yszx 下面那个是错的,但是上面的是对的.上面有解释,你不看

[yszx]

@yangyaofei 8 楼两个输出一个是[5,3],一个是[3,5]哎···我上面提到那么多次····