列车调度 堆栈 python

列车调度 堆栈 python列车调度描述题目分解1.全排列2.判断合法输出序列3.S容量小于A的情况,输出合法出栈序列4.输出操作5.输出操作完整可运行代码描述描述某列车调度站的铁道联接结构如Figure1所示其中,A为入口,B为出口,S为中转盲端。所有铁道均为单轨单向式:列车行驶的方向只能是从A到S,再从S到B;另外,不允许超车。因为车厢可在S中驻留,所以它们从B端驶出的次序,可能与从A端驶入的次序不同。不过S…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

描述

描述
某列车调度站的铁道联接结构如Figure 1所示

在这里插入图片描述
其中,A为入口,B为出口,S为中转盲端。所有铁道均为单轨单向式:列车行驶的方向只能是从A到S,再从S到B;另外,不允许超车。因为车厢可在S中驻留,所以它们从B端驶出的次序,可能与从A端驶入的次序不同。不过S的容量有限,同时驻留的车厢不得超过m节。
设某列车由编号依次为{1, 2, …, n}的n节车厢组成。调度员希望知道,按照以上交通规则,这些车厢能否以{a1, a2, …, an}的次序,重新排列后从B端驶出。如果可行,应该以怎样的次序操作?

输入
共两行。

第一行为两个整数n,m。

第二行为以空格分隔的n个整数,保证为{1, 2, …, n}的一个排列,表示待判断可行性的驶出序列{a1,a2,…,an}。

输出
若驶出序列可行,则输出操作序列,其中push表示车厢从A进入S,pop表示车厢从S进入B,每个操作占一行。

若不可行,则输出No。

样例
Example 1
Input

5 2
1 2 3 5 4
Output

push
pop
push
pop
push
pop
push
push
pop
pop
Example 2
Input
5 5
3 1 2 4 5
Output
No
限制
1 ≤ n ≤ 1,600,000
0 ≤ m ≤ 1,600,000

时间:2 sec
空间:256 MB

题目分解

这个问题可以分为几步:step1:求入栈序列的全排列 ;step2:根据出栈规则求合法的出栈序列;step3:若S的容量小于A,进行再一步的筛选 step4:输出序列 step5:输出操作

1.全排列

详细描述在这
https://blog.csdn.net/m0_38008539/article/details/95178298

提供两种方法

def perm_byOrder(stack_in,begin,end):
    """ 求全排列 -> 调换顺序的方法 :param lis: 需要求全排列的序列 :param begin: 移动变量 :param end: 固定变量 :return: 全排列 """
    if begin >= end: #结束标志
        stack_perm.append(copy.copy(stack_in))
        # print(stack_in)
    else:
        i = begin
        for num in range(begin,end):
            stack_in[num],stack_in[i] = stack_in[i],stack_in[num] #固定当前位置,在进行下一位的排列
            perm_byOrder(stack_in,begin+1,end)
            # 调用结束之后还需要回溯将交换位置的元素还原,以供其他下降路径使用(二叉树)
            stack_in[num],stack_in[i] = stack_in[i],stack_in[num]
def perm_bySlice(stack_in):
    """ 全排列 -> 利用切片的方法 :param stack_in: 需要求全排列的序列 :return: 全排列 """
    if len(stack_in) == 1: #结束条件
        return [stack_in]
    reslut = []
    for i in range(len(stack_in)):
        s = stack_in[:i] + stack_in[i+1:] #stack_in[i] 不仅如此下一次递归
        p = perm_bySlice(s)
        for x in p:
            reslut.append(stack_in[i:i+1] + x)
    return reslut

2.判断合法输出序列

也有两种方法

  • 方法1
    将入栈队列和出栈队列进行比较,引入辅助堆栈,将入栈数据和出栈队列进行比较,不相等则继续压栈,相等则辅助堆栈弹出,最后若辅助堆栈为空,证明序列合法
class stack():
    def __init__(self, length):
        self.length = length
        self.top = -1
        self.stack = []
    def noEmpty(self): #判断不为空
        if self.top == -1:
            return False
        else:
            return True
    def push(self,data):
        if self.top >= self.length:
            print('堆栈已满\n')
        else:
            self.top += 1
            self.stack.append(data)
    def top_value(self):
        return self.stack[self.top]
    def pop(self):
        if self.noEmpty() is False:
            print('堆栈是空的')
        else:
            self.stack.pop(self.top)
            # print('弹出的数据为:%d' % (self.stack.pop(self.top)))
            self.top -= 1
def judge_stack_byCompare(stack_out):
    """ 通过入栈序列和出栈序列的比较 :param stack_out: 要判断的序列 :return: True or False """
    stack_in = stack(len(stack_out))
    j = 0
    for i in range(len(stack_out)):
        stack_in.push(i + 1)
        while stack_in.noEmpty() and stack_out[j] == stack_in.top_value():
            stack_in.pop()
            j = j + 1

    if stack_in.noEmpty():
        return False  #出栈序列不合法
    else:
        return True #出栈序列合法
  • 方法2
    通过观察的方法以及出栈的规则,对于序列中的任意一个数其后面所有比他小的数应该是倒序的
def judge_stack_byOrder(stack_out):
    """ 对于序列中的任意一个数其后面所有比他小的数应该是倒序的 :param stack_out: 要判断的序列 :return: True or False """
    flag = 1
    b = [None]
    for i in range(len(stack_out)):
        k = 0
        for j in range(i+1,len(stack_out)):
            if stack_out[i] > stack_out[j]:  #在比data[i]的范围内讨论
                if k == 0: #相当于记录一个基准值,再和其他小于data[j]的数讨论
                    b[k] = stack_out[j] #记录比data[i]更小的数
                    k += 1
                else:
                    if stack_out[j] > b[0]:#出现了比记录值还大的数,更改标志
                        flag = 0
                    else:#记录更小的数
                        b[0] = stack_out[j]
    return flag

3.S容量小于A的情况,输出合法出栈序列

根据观察的方法,设S的容量为m,A序列为n 针对2中合法的序列,若其中某一元素后有至少m个小于它的,则该序列在此情况下不合法,即排除

def judge_for_m(stack_out):
    """ 中转盲站的容量有限,最多能容纳的节数可能会小于输入数据的节数,因此需要在 合法出栈的队列的基础上,在进一步判断 ->【对于序列中的某一个数,其后有两个数小于它,则排除】 :param stack_out: 需要进行判断的出栈队列 :return: """
    flag = 1
    for i in range(len(stack_out)):
        k = 0
        for j in range(i+1,len(stack_out)):
            if stack_out[i] > stack_out[j]: #找到后面比data[i]小的数
                k += 1 #计数
        if k >= m:
            flag = 0
    return flag

4.输出操作

def stack_correct(stacks,n,m):
    """ :param stacks: 全排列 :return: 对应m的条件下的合法出栈序列 """
    stack_correct= [] #m>=n时的合法序列
    stack_wrong = [] #m>=n时的非法序列
    stack_correct_advance = [] #m<n时的合法序列
    stack_wrong_advance = [] #m<n时的非法序列
    for data in stacks:
        # if judge_stack_byOrder(data):
        if judge_stack_byCompare(data):
            stack_correct.append(data)
        else:
            stack_wrong.append(data)
    # 在合法的出栈序列的基础上进一步筛选
    if m < n:
        for data in stack_correct:
            if judge_for_m(data):
                stack_correct_advance.append(data)
            else:
                stack_wrong_advance.append(data)
    return stack_correct,stack_wrong,stack_correct_advance,stack_wrong_advance

5.输出操作

针对某一具体的序列,进行输出操作步骤

def operate(stack_out):
    """ :param stack_out: 出栈序列 :return: 操作方法 当然也可以用于判断输出序列 """
    stack_in = stack(len(stack_out))
    j = 0
    for i in range(len(stack_out)):
        stack_in.push(i + 1)
        print('push %d' % (i + 1))
        while stack_in.noEmpty() and stack_out[j] == stack_in.top_value():
            print('pop %d' % (stack_in.top_value()))
            stack_in.pop()
            j = j + 1

完整可运行代码

import copy
stack_perm = []  #记录入栈序列的全排列
#定义栈的数据结构
class stack():
    def __init__(self, length):
        self.length = length
        self.top = -1
        self.stack = []
    def noEmpty(self): #判断不为空
        if self.top == -1:
            return False
        else:
            return True
    def push(self,data):
        if self.top >= self.length:
            print('堆栈已满\n')
        else:
            self.top += 1
            self.stack.append(data)
    def top_value(self):
        return self.stack[self.top]
    def pop(self):
        if self.noEmpty() is False:
            print('堆栈是空的')
        else:
            self.stack.pop(self.top)
            # print('弹出的数据为:%d' % (self.stack.pop(self.top)))
            self.top -= 1
def operate(stack_out):
    """ :param stack_out: 出栈序列 :return: 操作方法 当然也可以用于判断输出序列 """
    stack_in = stack(len(stack_out))
    j = 0
    for i in range(len(stack_out)):
        stack_in.push(i + 1)
        print('push %d' % (i + 1))
        while stack_in.noEmpty() and stack_out[j] == stack_in.top_value():
            print('pop %d' % (stack_in.top_value()))
            stack_in.pop()
            j = j + 1
def judge_stack_byCompare(stack_out):
    """ 通过入栈序列和出栈序列的比较 :param stack_out: 要判断的序列 :return: True or False """
    stack_in = stack(len(stack_out))
    j = 0
    for i in range(len(stack_out)):
        stack_in.push(i + 1)
        while stack_in.noEmpty() and stack_out[j] == stack_in.top_value():
            stack_in.pop()
            j = j + 1

    if stack_in.noEmpty():
        return False  #出栈序列不合法
    else:
        return True #出栈序列合法
def judge_stack_byOrder(stack_out):
    """ 对于序列中的任意一个数其后面所有比他小的数应该是倒序的 :param stack_out: 要判断的序列 :return: True or False """
    flag = 1
    b = [None]
    for i in range(len(stack_out)):
        k = 0
        for j in range(i+1,len(stack_out)):
            if stack_out[i] > stack_out[j]:  #在比data[i]的范围内讨论
                if k == 0: #相当于记录一个基准值,再和其他小于data[j]的数讨论
                    b[k] = stack_out[j] #记录比data[i]更小的数
                    k += 1
                else:
                    if stack_out[j] > b[0]:#出现了比记录值还大的数,更改标志
                        flag = 0
                    else:#记录更小的数
                        b[0] = stack_out[j]
    return flag
def recursive(num):
    """计算全排列的个数"""
    if num == 0:
        return 1
    else:
        return num * recursive(num-1)

def perm_byOrder(stack_in,begin,end):
    """ 求全排列 -> 调换顺序的方法 :param lis: 需要求全排列的序列 :param begin: 移动变量 :param end: 固定变量 :return: 全排列 """
    if begin >= end: #结束标志
        stack_perm.append(copy.copy(stack_in))
        # print(stack_in)
    else:
        i = begin
        for num in range(begin,end):
            stack_in[num],stack_in[i] = stack_in[i],stack_in[num] #固定当前位置,在进行下一位的排列
            perm_byOrder(stack_in,begin+1,end)
            # 调用结束之后还需要回溯将交换位置的元素还原,以供其他下降路径使用(二叉树)
            stack_in[num],stack_in[i] = stack_in[i],stack_in[num]
def perm_bySlice(stack_in):
    """ 全排列 -> 利用切片的方法 :param stack_in: 需要求全排列的序列 :return: 全排列 """
    if len(stack_in) == 1: #结束条件
        return [stack_in]
    reslut = []
    for i in range(len(stack_in)):
        s = stack_in[:i] + stack_in[i+1:] #stack_in[i] 不仅如此下一次递归
        p = perm_bySlice(s)
        for x in p:
            reslut.append(stack_in[i:i+1] + x)
    return reslut
def judge_for_m(stack_out):
    """ 中转盲站的容量有限,最多能容纳的节数可能会小于输入数据的节数,因此需要在 合法出栈的队列的基础上,在进一步判断 ->【对于序列中的某一个数,其后有两个数小于它,则排除】 :param stack_out: 需要进行判断的出栈队列 :return: """
    flag = 1
    for i in range(len(stack_out)):
        k = 0
        for j in range(i+1,len(stack_out)):
            if stack_out[i] > stack_out[j]: #找到后面比data[i]小的数
                k += 1 #计数
        if k >= m:
            flag = 0
    return flag

def stack_correct(stacks,n,m):
    """ :param stacks: 全排列 :return: 对应m的条件下的合法出栈序列 """
    stack_correct= [] #m>=n时的合法序列
    stack_wrong = [] #m>=n时的非法序列
    stack_correct_advance = [] #m<n时的合法序列
    stack_wrong_advance = [] #m<n时的非法序列
    for data in stacks:
        # if judge_stack_byOrder(data):
        if judge_stack_byCompare(data):
            stack_correct.append(data)
        else:
            stack_wrong.append(data)
    # 在合法的出栈序列的基础上进一步筛选
    if m < n:
        for data in stack_correct:
            if judge_for_m(data):
                stack_correct_advance.append(data)
            else:
                stack_wrong_advance.append(data)
    return stack_correct,stack_wrong,stack_correct_advance,stack_wrong_advance
if __name__ == '__main__':
    # 定义输入
    n = int(input('请输入需要调度火车厢的节数n:'))
    m = int(input('请输入中转盲站所能容纳的火车厢的节数m(可以>=n,也可以<n):'))
    stackA = list(range(1, n + 1))  # 入栈序列 ->不用类也可以 顺序序列,如果其他序列,可以使用换成索引
    perm_byOrder(stackA,0,len(stackA))  #计算全排列
    # stack_perm = perm_bySlice(stackA) #计算全排列
    print('可能出栈的序列为:',stack_perm)
    stack_correct,stack_wrong,stack_correct_advance,stack_wrong_advance = stack_correct(stack_perm,n,m)
    print('m>=n正确队列为:',stack_correct)
    print('m>=n错误队列为:',stack_wrong)
    print('m>=n正确序列应有个数(理论方法计算):',int((1/(n+1)) *(recursive(2*n)/(recursive(n)*recursive(n)))))
    print('m>=n正确序列实际个数:',len(stack_correct))
    print('m<n正确队列为【在m>=n正确队列的基础上】:',stack_correct_advance)
    print('m<n错误队列为【在m>=n正确队列的基础上】:',stack_wrong_advance)
    # 求某一具体序列的操作方法
    print('===========================================================')
    operate(stack_correct[0])
    print('===========================================================')

  1. 内存问题
    之前在定义记录全排列的数据的时候,定义了
stack_perm = [None] *recursive(num)

当num = 12 时 就出现了内存错误MemoryError,当num再大的时候,直接出现溢出错误OverFlow cannot fit ‘int’ into an index-sized integer:
因此这个地方需要注意
2.不提前定义大小直接使用append
会使电脑变得非常卡,占用内存太大

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159380.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Ubuntu18.04下安装搜狗输入法「建议收藏」

    Ubuntu18.04下安装搜狗输入法「建议收藏」首先,安装Fcitx输入框架sudoaptinstallfcitx其次,上搜狗输入法官网下载Linux版本搜狗输入法(32位和64位根据自己情况,在虚拟机上用浏览器下载即可然后进入相应的下载目录,进行安装(安装过程中如果有错,运行sudoapt–fix-brokeninstall)安装成功过后,进入设置根据红色箭头进入语言安装界面,安装语言(会自…

  • 断点调试原理

    断点调试原理调试断点原理   调试断点,依赖于父进程和子进程之间的通信,打断点实际是在被调试的程序中,改变断点附近程序的代码,这个断点使得被调试的程序,暂时停止,然后发送信号给父进程(调试器进程),然后父进程能够得到子进程的变量和状态。达到调试的目的。   修改断点附近程序的指令地址为0xcc,这个地址的指令就是int3,含义是,是当前用户态程序发生中断,告诉内核当前程序有断点,那么内核

  • 手机最强 Python 编程神器,在手机上运行 Python 不再是梦[通俗易懂]

    手机最强 Python 编程神器,在手机上运行 Python 不再是梦[通俗易懂]手机编程软件有很多,大部分都很难使用,操作不灵活,甚至不能安装第三方库。尝试安装了很多Python移动编程软件,发现了很多问题,不是编码效率低就是各种bug。今天,来自一位python编程小哥指导,向大家推荐两款精心挑选的手机编程软件,它们也是非常成熟的手机编程工具。QPythonOHQpython是一个轻量级的、成熟的python编程工具。它配有终端和简单的代码编辑器。它支持安装第三方库。目前,它支持Python3.6.6,这还不算太老。代码编辑区域代码比其他手机编程软件更灵活,底

  • 计算机发展史上代表性的人物,计算机发展史最具影响力人物「建议收藏」

    计算机发展史上代表性的人物,计算机发展史最具影响力人物「建议收藏」1.冯·诺依曼 1903-1957开创了现代计算机理论,其体系结构沿用至今,而且他早在40年代就已预见到计算机建模和仿真技术对当代计算机将产生的意义深远的影响2.蒂姆·伯纳斯·李  1955-互联网之父蒂姆·伯纳斯·李是万维网的发明人,也是万维网联盟(World Wide Web Consortium)的发起人。1990年,他在日内瓦的欧洲粒子物理实验室里开发出了世界上第一个网页浏览器。3.罗伯特…

    2022年10月18日
  • null toarray php,解决Laravel5.5下的toArray问题

    null toarray php,解决Laravel5.5下的toArray问题作为一个有轻度强迫症且受ThinkPHP影响较深的PHP码农,总觉得Laravel5.5的DB::xxoo->get()->toArray()之后竟然还没得到我想要的ThinkPHP中的select()出来的数组,于是决定做一下修改。PS:出于尽量不影响原有框架的考虑,我是新建了一个方法叫getList来暂代toArray那不知所谓的返回结果,在没有找到更好的解决办法之前,暂时这么用着…

  • 域渗透之NTLM Relay

    域渗透之NTLMRelay基础知识LLMNR概述链路本地多播名称解析(LLMNR)是一个基于协议的域名系统(DNS)数据包的格式,使得双方的IPv4和IPv6的主机来执行名称解析为同一本地链路

    2021年12月13日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号