设有6辆不同的列车顺序开入栈式站台问题

  1. 去年
    去年Sakura 重新编辑

    TIM图片20171029172048.jpg
    第一问,一共有多少种可能的出栈序列?
    我自己用计算机算出了结果是132,不知有方便的解法呢?

    附上代码,用穷举的方式算的

    train=6
    instack=0
    outstack=0
    global a
    a = 0
    
    def counts(train,instack,outstack):
        global a
        if train == 0:
            a = a + 1
            return 0
        if instack == 0:
            counts(train-1,instack+1,outstack)
        if instack > 0:
            counts(train-1,instack+1,outstack)
            counts(train,instack-1,outstack+1)
    
    counts(train,instack,outstack)
    print (a)
  2. 天马行空

    2楼 2017年10月30日 数学版主

    Catalan数.

  3. lh1962

    3楼 2017年10月30日 优秀回答者

    好久以前写过这个
    卡特兰数

  4. @lh1962 好久以前写过这个
    卡特兰数

    @天马行空 Catalan数.

    谢谢

  5. @lh1962 好久以前写过这个
    卡特兰数

    那对于一个出栈序列,如何检验其是否合法呢?当然模拟出入栈是个很有效的办法了,但合法的出栈序列有没有很好的判定性质呢

  6. lh1962

    6楼 2017年11月12日 优秀回答者

    @szy042 那对于一个出栈序列,如何检验其是否合法呢?当然模拟出入栈是个很有效的办法了,但合法的出栈序列有没有很好的判定性质呢

    应当是不存在模拟出入栈更快的办法了...毕竟这个序列长度也是$O(N)$

  7. 去年szy042 重新编辑

    @lh1962 应当是不存在模拟出入栈更快的办法了...毕竟这个序列长度也是$O(N)$

    这么说,一个合法的出栈序列会存在一些什么样的特殊性质?不一定非要复杂度更优

 

后才能发言