精华内容
下载资源
问答
  • 列车厢调度pta
    2019-09-18 19:26:55

    栈的简单应用

    #include <stdlib.h>
    #include <cstdio>
    #include <iostream>
    #include <queue>
    #include <stack>
    #include <string.h>
    #include <math.h>
    #include <algorithm>
    
    #define mem(t, v)   memset ((t) , v, sizeof(t))
    #define INF 0x3f3f3f3f
    #define eps 1e-8
    
    using namespace std;
    
    char in[30],out[30];
    int put[60],topp=0;
    stack<char>s;
    
    int main(){
        int flag=1;
        cin.getline(in,30);
        cin.getline(out,30);
        int i,j=0;
        int leni=strlen(in);
        int leno=strlen(out);
        for(i=0;i<leni;i++){
            //printf("%c %c\n",in[i],out[j]);
            if(in[i]==out[j]){
                put[topp++]=2;
                j++;
            }
            else {
                while(!s.empty()){
                    char t=s.top();
                    if(t==out[j]){
                        s.pop();
                        put[topp++]=0;
                        j++;
                    }
                    else break;
                }
                s.push(in[i]);
                put[topp++]=1;
            }
        }
        while(!s.empty()&&j<leno){
            char t=s.top();
            s.pop();
            put[topp++]=0;
            if(t!=out[j++]){
                flag=0;
                break;
            }
        }
    
        if(flag){
            for(int i=0;i<topp;i++){
                if(put[i]==2)printf("1->2\n");
                else if(put[i]==1){
                    if(put[i+1]==0){
                        printf("1->2\n");
                        i++;
                    }
                    else printf("1->3\n");
                }
                else printf("3->2\n");
            }
        }
        else {
            printf("Are you kidding me?\n");
        }
        return 0;
    }

     

    更多相关内容
  • PTA】7-1 列车厢调度

    2022-01-18 15:09:27
    7-1 列车厢调度 1 ====== <--移动方向 / 3 ===== \ 2 ====== -->移动方向 有三条平行的列车轨道(1、2、3)以及1-3和2-3两段连接轨道。现有一列车厢停在1号轨道上,请利用两条连接轨道以及3号轨道,将...

    7-1 列车厢调度

            1  ======   <--移动方向
         /
    3 =====  
         \
            2  ======   -->移动方向
    

    有三条平行的列车轨道(1、2、3)以及1-3和2-3两段连接轨道。现有一列车厢停在1号轨道上,请利用两条连接轨道以及3号轨道,将车厢按照要求的顺序转移到2号轨道。规则是:

    • 每次转移1节车厢;
    • 处在1号轨道的车厢要么经过1-3连接道进入3号轨道(该操作记为"1->3"),要么经过两条连接轨道直接进入2号轨道(该操作记为"1->2");
    • 一旦车厢进入2号轨道,就不可以再移出该轨道;
    • 处在3号轨道的车厢,只能经过2-3连接道进入2号轨道(该操作记为"3->2");
    • 显然,任何车厢不能穿过、跨越或绕过其它车厢进行移动。
      对于给定的1号停车顺序,如果经过调度能够实现2号轨道要求的顺序,则给出操作序列;如果不能,则输出 Are you kidding me?

    输入格式:
    两行由大写字母组成的非空字符串,第一行表示停在1号轨道上的车厢从左到右的顺序,第二行表示要求车厢停到2号轨道的进道顺序(输入样例1中第二行CBA表示车厢在2号轨道的停放从左到右是ABC,因为C最先进入,所以在最右边)。两行字符串长度相同且不超过26(因为只有26个大写字母),每个字母表示一节车厢。题目保证同一行内的字母不重复且两行的字母集相同。

    输出格式:
    如果能够成功调度,给出最短的操作序列,每个操作占一行。所谓“最短”,即如果1->2可以完成的调度,就不要通过1->3和3->2来实现。如果不能调度,输出 “Are you kidding me?”
    输入样例1:

    ABC
    CBA
    

    输出样例1:

    1->3
    1->3
    1->2
    3->2
    3->2
    

    输入样例2:

    ABC
    CAB
    

    输出样例2:

    Are you kidding me?
    

    思路:

    在该问题中,列车调度的过程可简化为两字符串中每个字符出栈入栈的问题。每当一列轨道1中的列车进入轨道3之后,检查所要求轨道2中的列车顺序。在每一次的检查中确定列车的操作序列。根据实验要求,共可列出以下几种情况:
    1.轨道3为空,若待进入轨道3的轨道1中的列车与轨道2中的目的列车不相同,则1->3,检查轨道1中下一列车。
    2.轨道3为空,若待进入轨道3的轨道1中的列车与轨道2中的目的列车相同,则1->2,检查轨道1中下一列车和轨道2中下一列车。
    3.轨道3不为空,若待进入轨道3的轨道1中的列车与轨道2中的目的列车相同,则1->2,检查轨道1中下一列车和轨道2中下一列车。
    4.轨道3不为空,若待进入轨道3的轨道1中的列车与轨道2中的目的列车相同,则1->2,检查轨道1中下一列车和轨道2中下一列车。
    5.轨道3不为空,若待进入轨道3的轨道1中的列车与轨道2中的目的列车不相同且轨道3中最外层列车与轨道2中目的列车相同,则3->2,检查轨道2中下一列车。
    6.轨道3不为空,若轨道1中无列车且轨道3中最外层列车与轨道2中目的列车不相同,则无法实现,结束程序。
    轨道3不为空,若待进入轨道3的轨道1中的列车与轨道2中的目的列车不相同,且轨道3中最外层列车与轨道2中目的列车不相同,则1->3,检查轨道1中下一列车。

    代码:

    #include<iostream>
    using namespace std;
    
    typedef struct {
    	int stacksize;
    	char *base;
    	char *top;
    }sqstack; 
    
    void initstack(sqstack &s)
    {
    	s.base = (char*)malloc(26*sizeof(char));
    	s.top = s.base;
    	s.stacksize = 26;
    }
    
    void push(sqstack &s,char a)
    {
    	*s.top++ = a;
    }
    
    void pop(sqstack &s,char &a)
    {
    	a = *(--s.top);
    }
    
    int empty(sqstack s)   //判断栈是否为空 
    {  if(s.top==s.base) return 1;
       else return 0;
    }
    
    char gettop(sqstack s)
    {
    	return *(s.top-1);
    }
    
    void print(int a[26])
    {
      for(int i=0;a[i]!='\0';i++)
        if(a[i]==1) printf("1->3\n");
        else if(a[i]==2) printf("1->2\n");
        else if(a[i]==3) printf("3->2\n");
    } 
    
    int main()
    {
    	sqstack l3, l2;
    	initstack(l3);
    	initstack(l2);
    	string a1,a2;
    	cin>>a1;
    	cin>>a2;
    	int i=0,j=0,k=0;
        static int a[26];
    	char z;
    	while(a1[i]!='\0' || a2[j]!='\0'){
    		if(empty(l3)) 
    		{
    			if(a1[i]!=a2[j])
    			{
    				a[k++] =1;
    				push(l3,a1[i]);
    				i++;
    				continue;
    			}
    			if(a1[i]==a2[j])
    			{
    				a[k++]=2;
    				push(l2,a1[i]);
    				i++;
    				j++;
    				continue;
    			}
    		}
    		if(!empty(l3)){
    			if(a1[i]==a2[j])
    			{
    				a[k++]=2;
    				push(l2,a1[i]);
    				i++;
    				j++;
    				continue;
    			}
    			if(a1[i]!=a2[j] && gettop(l3)==a2[j])
    			{
    				a[k++]=3;
    				pop(l3,z);
    				push(l2,z);
    				j++;
    				continue;
    			}
    			if(gettop(l3)!=a2[j] && a1[i]=='\0')
    			{
    				cout<<"Are you kidding me?"<<endl;
    				return 0;
    			}
    			if(a1[i]!=a2[j] && gettop(l3)!=a2[j])
    			{
    				a[k++] =1;
    				push(l3,a1[i]);
    				i++;
    				continue;
    			}
    		}
    	}
    	print(a);
    	return 0;
    }
    

    总结

    该题的关键在于要考虑到各字符匹配的各种可能情况。要理解各字符之间相同或不同代表的意义,从而得知列车调度的最短操作序列。在检查的过程中注意将信息存入一数组,这样在输出时使用print函数通过对数组总信息的读取即可完成操作序列的打印。

    展开全文
  • 问题遇到的现象和发生背景 问题相关代码,请勿粘贴截图 运行结果及报错内容 我的解答思路和尝试过的方法 我想要达到的结果 #include #include #include #define maxsize 26 typedef struct { char *base;...
  • PTA-7.1-列车厢调度(栈的应用)

    千次阅读 2020-10-23 17:17:59
    我们可以更具体地来讨论: ①假如1轨的栈顶就是C,显然C来自1轨 ②3轨栈顶就是C,则来自3轨 ③假如不是前两种情况,也不能断定调度出了错误,我们能做的只有把1轨的栈顶出栈,让他进到3轨 ④如果1轨已经空则无法...

    1.题目要求:

    题目点我

    2.思路解析:

    在这里插入图片描述

    样例如图:1-3轨道都可以看成是栈,不论是1轨还是3轨都应该让栈顶指向车厢在轨道的移动方向(因为栈的优点是在栈顶插入和删除元素很方便,反过来的话代码写起来会很麻烦)。

    结合图和题目要求的输入,两个输入都应该逆序入栈

    主要思路:

    由于输入给了原始车厢都在轨1的情况,和最终车厢都进入到轨2的顺序。我们可以从最终车厢都在轨2的情况入手,判断是否会出现不合理的情况。
    For example,第一个进入2轨的是C,则C可能有两种来源:①从1轨直接到2轨,②从3轨到2轨。
    我们可以更具体地来讨论:
    ①假如1轨的栈顶就是C,显然C来自1轨 ②3轨栈顶就是C,则来自3轨
    ③假如不是前两种情况,也不能断定调度出了错误,我们能做的只有把1轨的栈顶出栈,让他进到3轨
    ④如果1轨已经空则无法进行③的操作,可以直接输出“Are you kidding me?”

    再谈代码的思路:

    1.先定义一个标记int flag = 1;假定按输入的调度方式不会出现问题。当出问题了再将标记赋为0.
    2.以2轨最终状态为入手点,从第一个进2轨的到最后一个进2轨的 逐个遍历,按上面的①~④进行操作并逐个出栈——直到2轨中的元素全部出栈则代表没问题,或遇到④情况直接输出"Are you kidding me?"

    while(2轨不空)
    {
    	if(1轨栈顶 == 2轨栈顶)	//情况①
    	{
    		12轨栈顶元素出栈;
    		记录输出;
    	}
    	else if(3轨栈顶 == 2轨栈顶)//情况②
    	{
    		3/2轨栈顶元素出栈;
    		记录输出;
    	}
    	else if(1轨非空)//情况④
    	{
    		1轨栈顶元素出栈,并将其入到3;
    		记录输出;
    	}else//情况③
    	{
    		flag = 0;
    		break;
    	}
    }
    

    3.关于输出:由于在执行完while()循环之前你不知道他给出的调度顺序是正确的还是错误的,如果错误就只输出kidding而不输出1->2之类的操作序列了,应当把操作序列先存起来(比如用string数组)最后一块儿输出。

    3.代码:

    #include<iostream>
    #include<cstdio>
    #include<string>
    using namespace std;
    #define STACK_INIT_SIZE 100
    #define INCRESEMENT 10
    typedef char ElemType;
    typedef int Status;
    typedef struct Stack {
    	ElemType* top;
    	ElemType* base;
    	int stacksize;//当前已分配的存储空间
    }Stack;
    void StackInit(Stack& s) {//初始化
    	s.stacksize = STACK_INIT_SIZE;
    	s.top = s.base = (ElemType*)malloc(sizeof(ElemType) * s.stacksize);
    }
    void Push(Stack& s, ElemType e) {//入栈
    	if (s.top - s.base >= s.stacksize) {//栈满
    		s.base = (ElemType*)realloc(s.base, sizeof(ElemType) * (s.stacksize + INCRESEMENT));
    		s.top = s.base + s.stacksize;
    		s.stacksize += INCRESEMENT;
    	}
    	*s.top = e;
    	s.top++;
    }
    bool Empty(Stack s) {//判空
    	if (s.top == s.base)
    		return 1;
    	return 0;
    }
    ElemType Pop(Stack& s) {//返回值为弹出元素
    	if (Empty(s))
    		return '0';
    	else {
    		s.top--;
    		ElemType e = *s.top;
    		return e;
    	}
    }
    ElemType Top(Stack& s) {//返回栈顶元素
    	if (Empty(s))
    		return '0';
    	else {
    		ElemType e = *(s.top - 1);
    		return e;
    	}
    }
    int main() {
    	string a, b;
    	cin >> a >> b;
    	Stack s1, s2, s3;//三个轨道
    	StackInit(s1);
    	StackInit(s2);
    	StackInit(s3);
    	string road[100];//记录输出的路径
    	int cnt = 0;//有几行输出
    	int flag = 1;
    	for (int i = a.size()-1; i >= 0; i--) {//两组输入都要逆序入栈
    		Push(s1, a[i]);
    	}
    	for (int i = b.size()-1; i >= 0; i--) {
    		Push(s2, b[i]);
    	}
    	while (!Empty(s2)) {//2轨不空
    		if (!Empty(s1) && Top(s1) == Top(s2)) {//2轨的当前元素显然来自1轨
    			Pop(s1);
    			Pop(s2);
    			road[++cnt] = "1->2";
    		}
    		else if (!Empty(s3) && Top(s3) == Top(s2)) {//2轨的当前元素显然来自3轨
    			Pop(s3);
    			Pop(s2);
    			road[++cnt] = "3->2";
    		}
    		else if (Empty(s1)) {//没有别的选择,这个调度肯定是出了问题
    			flag = 0;
    			break;
    		}
    		else {//如果不是①②两种情况,不要断定出错,要先拖延时间
    			char e = Top(s1);
    			Pop(s1);
    			Push(s3,e);
    			road[++cnt] = "1->3";
    		}
    	}
    	if (!flag)
    		cout << "Are you kidding me?" << endl;
    	else {
    		for (int i = 1; i <= cnt; i++) {
    			cout << road[i] << endl;
    		}
    	}
    	return 0;
    }
    
    展开全文
  • pta列车厢调度

    2020-10-24 17:08:04
    列车厢调度 (15分) 1 ====== <--移动方向 / 3 ===== \ 2 ====== -->移动方向 大家或许在某些数据结构教材上见到过“列车厢调度问题”(当然没见过也不要紧)。今天,我们就来实际操作一下列车厢的调度...

    列车厢调度 (15分)

            1  ======   <--移动方向
             /
     3 =====  
             \
            2  ======   -->移动方向 
    

    大家或许在某些数据结构教材上见到过“列车厢调度问题”(当然没见过也不要紧)。今天,我们就来实际操作一下列车厢的调度。对照上方的ASCII字符图,问题描述如下:

    有三条平行的列车轨道(1、2、3)以及1-3和2-3两段连接轨道。现有一列车厢停在1号轨道上,请利用两条连接轨道以及3号轨道,将车厢按照要求的顺序转移到2号轨道。规则是:

    每次转移1节车厢;
    处在1号轨道的车厢要么经过1-3连接道进入3号轨道(该操作记为"1->3"),要么经过两条连接轨道直接进入2号轨道(该操作记为"1->2");
    一旦车厢进入2号轨道,就不可以再移出该轨道;
    处在3号轨道的车厢,只能经过2-3连接道进入2号轨道(该操作记为"3->2");
    显然,任何车厢不能穿过、跨越或绕过其它车厢进行移动。
    对于给定的1号停车顺序,如果经过调度能够实现2号轨道要求的顺序,则给出操作序列;如果不能,就反问用户 Are(你) you(是) kidding(凯丁) me(么)?

    输入格式:
    两行由大写字母组成的非空字符串,第一行表示停在1号轨道上的车厢从左到右的顺序,第二行表示要求车厢停到2号轨道的进道顺序(输入样例1中第二行CBA表示车厢在2号轨道的停放从左到右是ABC,因为C最先进入,所以在最右边)。两行字符串长度相同且不超过26(因为只有26个大写字母),每个字母表示一节车厢。题目保证同一行内的字母不重复且两行的字母集相同。

    输出格式:
    如果能够成功调度,给出最短的操作序列,每个操作占一行。所谓“最短”,即如果1->2可以完成的调度,就不要通过1->3和3->2来实现。如果不能调度,输出 “Are you kidding me?”

    输入样例1:

    ABC
    CBA
    输出样例1:
    1->3
    1->3
    1->2
    3->2
    3->2
    输入样例2:
    ABC
    CAB
    输出样例2:
    Are you kidding me?
    
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N=30; 
    char one[N];
    char two[N];		//这个地方写错了,two表示3号车道
    char goal[N];		//goal表示2号车道
    int Move[100000][2];
    
    int main()
    {
    	cin>>one;
    	cin>>goal;
    	int len=strlen(one);
    	int t1=0;
    	int t2=0;
    	int tg=0;
    	int tm=0;
    	
    	while(t1<len){
    		if(one[t1]==goal[tg]){
    			Move[tm][0]=1;
    			Move[tm][1]=2;
    			tm++;
    			t1++;
    			tg++;
    		}
    		else if(t2>0&&two[t2-1]==goal[tg]){
    			Move[tm][0]=3;
    			Move[tm][1]=2;
    			t2--;
    			tm++;
    			tg++;
    		}
    		else{
    			Move[tm][0]=1;
    			Move[tm][1]=3;
    			two[t2]=one[t1];
    			tm++;
    			t1++;
    			t2++;
    		}
    	}
    	int flag=0;
    	while(t2>0){
    		if(two[t2-1]==goal[tg]){
    			Move[tm][0]=3;
    			Move[tm][1]=2;
    			tm++;
    			t2--;
    			tg++;
    		}
    		else{
    			cout<<"Are you kidding me?"<<endl;
    			flag=1; 
    			break;
    		}
    	}
    	if(flag==0){
    		for(int i=0;i<tm;i++){
    			cout<<Move[i][0]<<"->"<<Move[i][1]<<endl;
    		}
    	}
    	
    	return 0;
    }
    
    展开全文
  • 大家或许在某些数据结构教材上见到过“列车厢调度问题”(当然没见过也不要紧)。今天,我们就来实际操作一下列车厢的调度。对照上方的ASCII字符图,问题描述如下: 有三条平行的列车轨道(1、2、3)以及1-3和...
  • PTA 列车调度 python

    2022-03-18 15:10:36
    火车调度PTA python实现 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2...
  • 这个题其实和 -出栈序列的合法性- 这个题类似,他们俩个用的都是同一个方法 #include<bits/stdc++.h> using namespace std; int main() { //总共三种操作,1--从1号轨道到2号轨道 //2--从1号轨道到3号轨道 ...
  • 5-19 列车厢调度 (25分) 1 ====== 移动方向 / 3 ===== \ 2 ====== -->移动方向 大家或许在某些数据结构教材上见到过“列车厢调度问题”(当然没见过也不要紧)。今天,我们就来实际操作一下列车厢...
  • PTA列车调度】Java

    2021-01-10 11:30:08
    列车调度 火车站的列车调度铁轨的结构如下图所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟...
  • PTA 题目 列车调度

    千次阅读 2020-03-27 12:53:31
    火车站的列车调度铁轨的结构如下图所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在...
  • PTA7-1 列车厢调度

    2021-10-24 22:08:50
    大家或许在某些数据结构教材上见到过“列车厢调度问题”(当然没见过也不要紧)。今天,我们就来实际操作一下列车厢的调度。对照上方的ASCII字符图,问题描述如下: 有三条平行的列车轨道(1、2、3)以及1-3和2-3两...
  • PTA 7-1 列车厢调度 1 ====== <–移动方向 / 3 ===== 2 ====== -->移动方向 大家或许在某些数据结构教材上见到过“列车厢调度问题”(当然没见过也不要紧)。今天,我们就来实际操作一下列车厢的调度。...
  • PTA 列车调度 Java

    千次阅读 2020-02-06 15:41:29
    PTA 列车调度 Java 火车站的列车调度铁轨的结构如下图所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在...
  • PTA 7-3 列车厢调度 (25 分)

    千次阅读 2019-05-24 07:47:27
    大家或许在某些数据结构教材上见到过“列车厢调度问题”(当然没见过也不要紧)。今天,我们就来实际操作一下列车厢的调度。对照上方的ASCII字符图,问题描述如下: 有三条平行的列车轨道(1、2、3)以及1...
  • pta 习题集5-19 列车厢调度

    千次阅读 2017-03-12 16:33:08
    大家或许在某些数据结构教材上见到过“列车厢调度问题”(当然没见过也不要紧)。今天,我们就来实际操作一下列车厢的调度。对照上方的ASCII字符图,问题描述如下: 有三条平行的列车轨道(1、2、3)以及1-3和2-3...
  • 列车厢调度(栈)

    2018-12-19 16:11:35
    7-9 列车厢调度 (25 分) 1 ====== &lt;--移动方向 / 3 ===== \ 2 ====== --&gt;移动方向 大家或许在某些数据结构教材上见到过“列车厢调度问题”(当然没见过也不要紧)。今天,我们就来实际...
  • 7-5 列车厢调度 (25 分)

    千次阅读 2019-07-16 14:55:55
    7-5 列车厢调度 (25 分) 1 ====== <--移动方向 / 3 ===== \ 2 ====== -->移动方向 大家或许在某些数据结构教材上见到过“列车厢调度问题”(当然没见过...
  • 代码新,易懂 适合数据结构学习者参考。本课程设计的目的 (1)使学生熟练掌握抽象数据类型的组织和定义; (2)使学生熟练掌握数据类型的定义和实现(基于C/C++); (3)培养学生组织和分析数据的能力;...
  • PTA(列车厢调度) 代码: Rails 题意: A顺序1-n,给出到达B的顺序。中间可以先放到station,但是从station中只能从顶端取出。 经典模拟栈: 基本思想: 一个指向A,一个指向B,如果pa=pb,直接从A移动到B。...

空空如也

空空如也

1 2 3
收藏数 45
精华内容 18
关键字:

列车厢调度pta