欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Catalan数与出栈顺序个数,Java编程模拟

程序员文章站 2023-12-25 18:31:09
问题描述: 分析:对于每一个数字i, 在它入栈之前都有 i - 1 个数字通过栈到输出队列out(不用考虑这i - 1个数字的进出栈顺序,因为可以把它们抽象成f(i - 1)), 在它之后又有 n - i个 数字入栈然后出栈(同样不需要考虑它们的进出栈顺序),这样就得到对每个最后出栈的整数i,它都有 ......

问题描述:

队列中有从1到7(由小到大排列)的7个整数,问经过一个整数栈后,出栈的所有排列数有多少?
如果整数栈的容量是4(栈最多能容纳4个整数),那么出栈的排列数又是多少?


分析:对于每一个数字i, 在它入栈之前都有 i - 1 个数字通过栈到输出队列out(不用考虑这i - 1个数字的进出栈顺序,因为可以把它们抽象成f(i - 1)), 在它之后又有 n - i个 数字入栈然后出栈(同样不需要考虑它们的进出栈顺序),这样就得到对每个最后出栈的整数i,它都有f(i - 1)*f(n - i)种出栈顺序,求和就是n个数字顺序经过栈的出栈顺序了。

public class Catalan {

    public static int answers = 0;

    //请实现go函数
    public static void go(Deque from, Deque to, Stack s) {
        if(from.size() == 0 && s.empty()) {
            answers++;
        }
        else{
            Stack s1 = s.clone();
            Stack s2 = s.clone();
           // Deque from1 = from.clone();
           // Deque from2 = from.clone();
            if(from.size() != 0)
            {
                s1.push(from.getFirst());
                from.removeFirst();
                go(from, to , s1);
                from.addFirst(s1.pop());
            }

            if(!s2.empty())
            {
                to.addLast(s2.pop());
                go(from, to , s2);
            }
        }
    }

    public static void main(String[] args) {
        Deque from = new Deque();
        Deque to = new Deque();
        Stack s = new Stack();

        for(int i=1;i<=7;i++) {
            from.addLast(i);
        }

        go(from, to, s);

        System.out.println(answers);


    }

}

上一篇:

下一篇: