精华内容
下载资源
问答
  • 出栈次序

    千次阅读 2018-03-26 15:58:29
    标题:出栈次序 X星球特别讲究秩序,所有道路都是单行线。 一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。 路边有个死胡同,只能容一辆车通过,是临时的检查站,如图【p1.png】所示。 ...
    标题:出栈次序


        X星球特别讲究秩序,所有道路都是单行线。
    一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。
        路边有个死胡同,只能容一辆车通过,是临时的检查站,如图【p1.png】所示。
        X星球太死板,要求每辆路过的车必须进入检查站,也可能不检查就放行,也可能仔细检查。
        如果车辆进入检查站和离开的次序可以任意交错。那么,该车队再次上路后,可能的次序有多少种?
        为了方便起见,假设检查站可容纳任意数量的汽车。
        显然,如果车队只有1辆车,可能次序1种;2辆车可能次序2种;3辆车可能次序5种。
        现在足足有16辆车啊,亲!需要你计算出可能次序的数目。

        这是一个整数,请通过浏览器提交答案,不要填写任何多余的内容(比如说明性文字)。



    看似很复杂,其实只是问给你一组数据有多少种出栈顺序,这一分析一下子简单了许多,应为已经有大神对这种出栈顺序进行总结,其实有一个公式可以用

    推到过程如下:(仅供参考)

    如果元素a在1号位置,那么只可能a进栈,马上出栈,此时还剩元素b、c、d等待操作,就是子问题f(3) 
    2) 如果元素a在2号位置,那么一定有一个元素比a先出栈,即有f(1)种可能顺序(只能是b),还剩c、d,即f(2) 
    3) 如果元素a在3号位置,那么一定有两个元素比1先出栈,即有f(2)种可能顺序(只能是b、c),还剩d,即f(1) 
    4) 如果元素a在4号位置,那么一定是a先进栈,最后出栈,那么元素b、c、d的出栈顺序即是此小问题的解,即 f(3)

    结合所有情况,即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3) 
    为了规整化,我们定义f(0) = 1;于是f(4)可以重新写为: 
    f(4) = f(0) * f(3) + f(1) * f(2) + f(2) * f(1) + f(3) * f(0) 
    然后我们推广到n,推广思路和n=4时完全一样,于是我们可以得到: 
    f(n) = f(0)*f(n-1) + f(1)*f(n-2) + … + f(n-1)*f(0) 

    推导过程可以不太懂,但是记住 f(n) = f(0)*f(n-1) + f(1)*f(n-2) + … + f(n-1)*f(0)  就可以了,记住这个公式,出栈顺序一下简单了许多不需要深入进行计算,当然这只对计算出栈种类计算有用,如果需要深入计算的题目,就不能偷懒啦。


    计算的过程如下:

    # include <stdio.h>
    int fun(int n )
    {
    int i,j ,sum=0;
    i=0,
    j=n;
    if(n==1 || n==0)
    {
    return 1;
    }
    if(n==2)
    {
    return 2;
    }
    for(i=0 ;i<n;i++)
    {
    sum+=fun(i)*fun(n-i-1);
    }
    return sum ;
    }


    main ()
    {
    int i ; 

    scanf("%d",&i);
    printf("%d",fun(i));
    return 0;
    }





    展开全文
  • #include <stdio.h> #include <stack> #include <queue> ...bool check_is_valid_order(std::queue<...//获得测试队列,即出栈次序的长度 for (int i = 1; i <= n; i++){ S.push(i);//将1.
    #include <stdio.h>
    
    #include <stack>
    #include <queue>
    
    bool check_is_valid_order(std::queue<int> &order){
    	std::stack<int> S;//临时栈
    	int n = order.size();//获得测试队列,即出栈次序的长度
    	for (int i = 1; i <= n; i++){
    		S.push(i);//将1,2,3,4,5,6,7,8......入栈
    		while(!S.empty() && order.front() == S.top()){//如果栈S不为空,且 测试队列的头 == 栈顶
    			S.pop();//栈顶和队列头同时弹出
    			order.pop();
    		}
    	}
    	if (!S.empty()){//如果栈S不为空,说明测试队列的次序 不满足合法出栈次序
    		return false;
    	}
    	return true;
    }
    
    int main(){
    	int n;
    	int train;
    	scanf("%d", &n);
    	while(n){
    		scanf("%d", &train);
    		while (train){
    			std::queue<int> order;
    			order.push(train);
    			for (int i = 1; i < n; i++){
    				scanf("%d", &train);
    				order.push(train);
    			}
    			if (check_is_valid_order(order)){
    				printf("Yes\n");
    			}
    			else{
    				printf("No\n");
    			}
    			scanf("%d", &train);
    		}
    		printf("\n");
    		scanf("%d", &n);
    	}
    	return 0;
    }
    

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 在一般软件研发的笔试中,就会经常遇到关于入栈次序一定时,出栈次序有哪些?共有几种? 其实,此处只要了解一下卡特兰数的算法结构,参见: 卡特兰数 由卡特兰数的思想可知。若有n个元素顺序入栈,则对应的出栈次序...

    学过数据结构的程序猿应该都清楚,栈是一种先入后出,后入先出(LIFO)的表。即插入和删除都只能在一个位置上进行,即栈顶位置。对栈的基本操作有Push(入栈)和Pop(出栈)。在一般软件研发的笔试中,就会经常遇到关于入栈次序一定时,出栈次序有哪些?共有几种?

    其实,此处只要了解一下卡特兰数的算法结构,参见:

    卡特兰数

    由卡特兰数的思想可知。若有n个元素顺序入栈,则对应的出栈次序共有f(n)=f(0)f(n-1)+f(1)f(n-2)+……+f(n-1)f(0)

    (其中f(0)=1;f(1)=1);

    举个例子:

    如果说入栈元素次序是abc,则由递推公式可得出栈次序共有5种。出栈顺序分别如下:

    abc push pop push pop push pop a入栈→a出栈→b入栈→b出栈→c入栈→c出栈

    acb push pop push push pop pop a入栈→a出栈→b入栈→c入栈→c出栈→b出栈

    bac push push pop pop push pop a入栈→b入栈→b出栈→a出栈→c入栈→c出栈

    bca push push pop push pop pop a入栈→b入栈→b出栈→c入栈→c出栈→a出栈

    cba push push push pop pop pop a入栈→b入栈→c入栈→c出栈→b出栈→a出栈

    展开全文
  • day31 出栈次序

    2021-02-15 09:14:52
    出栈次序 X星球特别讲究秩序,所有道路都是单行线。 一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。 路边有个死胡同,只能容一辆车通过,是临时的检查站,如图【p1.png】所示。 X星球太...

    出栈次序

    X星球特别讲究秩序,所有道路都是单行线。
    
    一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。
    路边有个死胡同,只能容一辆车通过,是临时的检查站,如图【p1.png】所示。
    X星球太死板,要求每辆路过的车必须进入检查站,也可能不检查就放行,也可能仔细检查。
    如果车辆进入检查站和离开的次序可以任意交错。
    那么,该车队再次上路后,可能的次序有多少种?
    
    为了方便起见,假设检查站可容纳任意数量的汽车。
    显然,如果车队只有1辆车,可能次序1种;2辆车可能次序2种;3辆车可能次序5种。
    现在足足有16辆车啊,亲!需要你计算出可能次序的数目。
    这是一个整数,请通过浏览器提交答案,不要填写任何多余的内容(比如说明性文字)。    
    

    解题:卡特兰数

    可以将k辆车分解成两段,第k辆车的排序为每一种分成两段方法下,每段排序可能的乘积

    比如16辆车时,我们可以把它分成前4辆和后12辆,先计算前四辆的可能,再乘以后12辆的可能。当然16辆车还可以分成2+14,3+13等,每种都要统计

    数学公式为 h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (n>=2)

    这里用递推,递归纵深不够

    lst = [0]*17
    lst[0] = 1
    lst[1] = 1
    lst[2] = 2
    for i in range(3, 17):
        count = 0
        for j in range(i):
            count += lst[j]*lst[i-j-1]
        lst[i] = count
    print(lst[16])
    

    在这里插入图片描述

    展开全文
  • LQBv43-Python:出栈次序

    2021-02-15 20:03:55
    2014-/National_C_C++_B/2、出栈次序 标题:出栈次序 X星球特别讲究秩序,所有道路都是单行线。 一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。 路边有个死胡同,只能容一辆车通过,是...
  • 出栈次序 X星球特...
  • C语言 · 出栈次序

    2017-04-08 20:02:00
    标题:出栈次序 X星球特别讲究秩序,所有道路都是单行线。一个甲壳虫车队,共16辆车,按照编号先后发车, 夹在其它车流中,缓缓前行。 路边有个死胡同,只能容一辆车通过,是临时的检查站,如图【p1.png】所示。...
  • 标题:出栈次序 X星球特别讲究秩序,所有道路都是单行线。 一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。 路边有个死胡同,只能容一辆车通过,是临时的检查站,如图【p1.png】所示。 ...
  • 出栈次序 D:做一道简单的题目 X星球特别讲究秩序,所有道路都是单行线。 一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。 路边有个死胡同,只能容一辆车通过,是临时的检查站,如图...
  • 【蓝桥杯】出栈次序(递归、公式两种解法)。很好理解的递归。
  • 学过数据结构的程序猿应该...在一般软件研发的笔试中,就会经常遇到关于入栈次序一定时,出栈次序有哪些?共有几种? 其实,此处只要了解一下卡特兰数的算法结构,参见: http://baike.baidu.com/link?url=T7ZR16yiaWKN
  • 蓝桥杯 出栈次序

    2021-02-16 15:38:32
    目录问题描述思路分析及代码实现 问题描述 X星球特别讲究秩序,所有道路都是单行线。 一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。...显然,如果车队只有1辆车,可能次序1种

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 554
精华内容 221
关键字:

出栈次序