首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和流程图,请将流程图中(1)~(5)空缺处的内容填补完整。 [说明] 某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和
阅读下列算法说明和流程图,请将流程图中(1)~(5)空缺处的内容填补完整。 [说明] 某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和
admin
2010-01-15
66
问题
阅读下列算法说明和流程图,请将流程图中(1)~(5)空缺处的内容填补完整。
[说明]
某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。
(1)e0和e1表示底盘分别进入装配线0和装配线1所需要的时间。
(2)每条装配线有n个工位,第一条装配线的工位为S0,0,S0,1,…,S0,n-1,第二条装配线的工位为 S1,0,S1,1,…,S1,n-1。其中S0,k和S1,k(0≤k≤n-1)完成相同的任务,但所需时间可能不同。
(3)ai,j表示在工位Si,j处的装配时间,其中i表示装配线(i=0或i=1),j表示工位号(0≤j≤n-1)。
(4)ti,j表示从Si,j处装配完成后转移到另一条装配线下一个工位的时间。
(5)x0和x1表示装配结束后,汽车分别从装配线0和装配线1下线所需要的时间。
(6)在同一条装配线上,底盘从一个工位转移到其下一个工位的时间可以忽略不计。
图4-17所示的流程图描述了求最短装配时间的算法,该算法的输入为:
n:表示装配线上的工位数;
e
:表示e1和e2,i取值为0或1;
a
[j]:表示ai,j,i的取值为0或1,j的取值范围为0~n-1;
t
[j]:表示ti,j,i的取值为0或1,j的取值范围为0~n-1;
x
:表示x0和x1,i取值为0或1。
算法的输出为:
fi:最短的装配时间;
li:获得最短装配时间的下线装配线号(0或者1)。
算法中使用的f
[j]表示从开始点到Si,j处的最短装配时间。
选项
答案
这是一道考查动态规划算法求解最优汽车装配线的分析题。当问题具有两个特性,即最优子结构和重叠子问题时,可以考虑用动态规划算法求解问题。用动态规划算法求解具体应用问题具有以下4个步骤。 ①刻画问题的最优子结构,描述问题的最优解包含子问题的最优解。对于本试题,最短装配时间等于经过装配线0的第n个工位的最短装配时间加上x[0],或者等于经过装配线1的第n个工位的最短装配时间加上x[1],取哪条装配线取决于哪个值更小。而经过某条装配线0/1的第i个工位的最短装配时间又等于经过本条装配线第i-1个工位的最短装配时间,或者等于经过另一条装配线第i-1个工位的最短装配时间加上从这个工位到装配线0/1的迁移时间,取决于哪个值更小。 ②建立最优子结构的递归关系,这是关键的一步。对于本试题,可建立如下的递归关系。 [*] 由此可得,初始化数据时,(1)空缺处所填写的内容是f[0][0]=e[0]+a[0][0]和f[1][0]=e[1]+a[1][0]。 (2)空缺处所填写的内容可由该空缺处所在的条件判断框的“真”执行语句框中的内容——“f[0][j-1]+a[0][j]得到启发。而(3)空缺处所在条件判断框的填写内容可由(2)空缺处所在的条件判断框内容得到启发,即f[1][j-1]+a[1]刚<=f[O][j-1]+t[0][j-1]+a[1][j]或其他等价形式。 ③根据递归关系求最优解的值。由图4-17流程图最后一个条件判断框中信息“f[0][n-1]+x[0]<= f[1][n-1]+x[1]?”可知,最优解记录在fi中,fi=min(f(0,n-1)+xO,f(1,n-1)+x1),即(4)空缺处所填写的内容是最短的装配时间fi=f[O][n-1]+x[0]和获得最短装配时间的下线装配线号li=0,(5)空缺处所填写的内容是fi=f[1][n-1]+x[1]和li=1。 ④构造最优解。对于本试题来说,只是求出最优解是从哪条装配线装配出来,并没有记录最优解。
解析
转载请注明原文地址:https://kaotiyun.com/show/60DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
RUP在每个阶段都有主要目标,并在结束时产生一些制品。在(30)结束时产生“在适当的平台上集成的软件产品”。
在计算机系统中,系统的______可以用MTTF/(1+MTTF)来度量,其中MTTF为平均无故障时间。
某企业的生产流水线上有2名工人P1和P2,1名检验员P3。P1将初步加工的半成品放入半成品箱B1;P2从半成品箱B1取出继续加工,加工好的产品放入成品箱B2;P3从成品箱B2取出产品检验。假设B1可存放n件半成品,B2可存放m件产品,并设置6个信号量S1、
在分层体系结构中,(41)实现与实体对象相关的业务逻辑。在基于Java,EE技术开发的软件系统中,常用(42)技术来实现该层。(41)
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数已经排好序,将第i个整数依次和第i-1,i-2,…个整数进行比较,找到应该插入的位置。现采用插入排序算法对6个整数{5,2,4,6,1,3}进行从小到大排序,则需要进行(31)
线性表采用单循环链表存储的主要优点是_______。
编写测试计划的目的是______。①测试工作顺利进行②使项目参与人员沟通更舒畅③使测试工作更加系统化④软件过程规范化的要求⑤控制软件质量
关于汇编语言,以下叙述中正确的是(20)。
对某商店业务处理系统采用数据流图(DFD)进行功能建模,其中“检查订货单”是其中的一个①。由于在进行订货单检查时,需要根据客户的欠款情况、订单金额等多个条件判断是否采取发出催款单、准备货物、发出发货单等行为,此时适合采用②进行描述。②处
某软件公司在招聘软件评测师时,应聘者甲向公司做如下保证:①经过自己测试的软件今后不会再出现问题;②在工作中对所有程序员一视同仁,不会因为在某个程序员编写的程序中发现的问题多,就重点审查该程序,以免不利于团结;③承诺不需要其他人员,自己就可以独立进行测
随机试题
背景北京某工程据统计混凝土实物工作量约为23000m3,混凝土为商混不考虑现场搅拌,混凝土养护用水定额取700L/m3;拟定结构及前期阶段施工工期为300d;每天按照1.5个工作班计算。其中:K1=1.1,Q1=23000m3,N1=750L/m3,T
电算化档案资料管理的要求是什么?
锅炉压力容器与其他设备相比容易(),因此容易发生事故。
某单元格数据是文本格式的邮政编码,下列单元格的邮编输入方式正确的是______。
有关血液功能的叙述,正确的是
1999年10月1日,甲公司的退休职工王某在退休后6个月完成了一项方法发明创造,甲公司认为王某的发明与其在甲公司承担的本职工作有关,向王某提出该方法发明申请专利的权利属于甲公司,王某表示同意。2000年1月1日,甲公司向国务院专利行政部门提出发明专利的书面
以出让方式取得土地使用权的,属于房屋建设工程的,完成开发投资总额的()以上才可以进行建设用地使用权的转让。
发展社会主义民主政治,最根本的是要把()有机统一起来。
发展中国特色社会主义文化要坚持“两为”方向和“双百”方针。()
1963年,周恩来将我们党提出的一系列和平解决台湾问题的思想、政策和主张归纳为“一纲四目”。“一纲”即台湾必须统一于中国。“四目”为
最新回复
(
0
)