V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
yangyaofei
V2EX  ›  问与答

一个算法题请教....

  •  
  •   yangyaofei · 2016-09-18 21:45:43 +08:00 · 2991 次点击
    这是一个创建于 2967 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如下,判断题:

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

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

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

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

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

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

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

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

    17 条回复    2016-09-19 13:08:03 +08:00
    shliujing
        1
    shliujing  
       2016-09-18 22:09:27 +08:00   ❤️ 1
    标题描述不清,正文描述看着有点累 0 0
    yszx
        2
    yszx  
       2016-09-18 22:25:16 +08:00
    上一个:放 5 个取 5 个和放 2 个再放 3 个再取 5 个的结果是一样的

    下一个:放 2 取 2 放 3 取 3 和放 3 取 3 放 2 取 2 是不同的
    yangyaofei
        3
    yangyaofei  
    OP
       2016-09-18 22:25:29 +08:00
    @shliujing 啊,写的比较乱凑合看一下吧.
    yangyaofei
        4
    yangyaofei  
    OP
       2016-09-18 22:26:47 +08:00
    @yszx 放两个再防三个和放五个有区别??大哥别闹.....
    yszx
        5
    yszx  
       2016-09-18 22:28:34 +08:00
    @yangyaofei 当然没区别,但是这两是不同的组合啊
    whwq2012
        6
    whwq2012  
       2016-09-18 22:29:17 +08:00 via Android
    @yangyaofei 然后这两个出来,三个再进去啊
    yangyaofei
        7
    yangyaofei  
    OP
       2016-09-18 22:31:27 +08:00
    @yszx 00001111 和 00 00 1111 是不同的序列? 蛤蛤和蛤 蛤 不是一个蛤?别闹
    @whwq2012 黑人问号.jpg
    zhy0216
        8
    zhy0216  
       2016-09-18 22:34:59 +08:00   ❤️ 1
    以 [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
        9
    yszx  
       2016-09-18 22:35:40 +08:00
    @yangyaofei 是不同的“组合”啊····执行不同的入栈出栈组合操作。出入的序列当然相同,不相同这题答案不就是“错”么。就是不同的入栈出栈组合效果相同的意思啊
    yszx
        10
    yszx  
       2016-09-18 22:37:07 +08:00
    @yangyaofei 当然作为程序连在一起是一样的····要么就是我搞错了
    yangyaofei
        11
    yangyaofei  
    OP
       2016-09-18 22:40:40 +08:00
    @zhy0216 哦~~我明白了!!!谢谢谢谢.思维定式认定非要所有的元素都要进行 push 和 pop 了,茅塞顿开,谢谢谢谢

    @yszx 大哥别闹,你那个"组合"并不是题目中说的组合,谢谢.有网友解答我了,同样谢谢你,但是你说的不对.
    yszx
        12
    yszx  
       2016-09-18 22:44:29 +08:00
    @yangyaofei [3,5]和[5,3]哎····还是说题目说的是栈里面一样····
    yangyaofei
        13
    yangyaofei  
    OP
       2016-09-18 22:48:46 +08:00
    @yszx 是输出的序列,比如 12345 你 pu po pu po 之后的序列是 12 说的是 12345 一样 12 一样... pu po pu po 这个不一样.....
    yszx
        14
    yszx  
       2016-09-18 22:54:04 +08:00
    @yangyaofei 那么至少 [5 , 3] 和 [3 , 5] 是不一样的····
    yszx
        15
    yszx  
       2016-09-19 02:27:15 +08:00
    @yangyaofei 好吧···我去搜题目了,然后在别的地方看到这个题目答案是 错。

    假如按你这样的条件,绝对不可能相同,因为相同的输出,就要求出栈的位置和顺序完全相同,那么中间填充的入栈也必然相同。
    比如说[1,3,5 , 7]现在要求第一个出栈 5 ,那么只有入栈 1 ,入栈 3 ,入栈 5 这一条路。因为如果不入栈就到不了 5 ,如果继续出栈,则必然会在 5 之前就有出栈。
    yangyaofei
        16
    yangyaofei  
    OP
       2016-09-19 12:44:02 +08:00
    @yszx 下面那个是错的,但是上面的是对的.上面有解释,你不看
    yszx
        17
    yszx  
       2016-09-19 13:08:03 +08:00
    @yangyaofei 8 楼两个输出一个是[5,3],一个是[3,5]哎···我上面提到那么多次····
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2841 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 14:28 · PVG 22:28 · LAX 07:28 · JFK 10:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.