首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和流程图,请将流程图中(1)~(5)空缺处的内容填补完整。 [说明] 某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和
阅读下列算法说明和流程图,请将流程图中(1)~(5)空缺处的内容填补完整。 [说明] 某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和
admin
2010-01-15
73
问题
阅读下列算法说明和流程图,请将流程图中(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)结束时产生“在适当的平台上集成的软件产品”。
以下属于测试停止依据的是______。①测试用例全部执行结束②测试覆盖率达到要求③测试超出了预定时间④查出了预定数目的故障⑤执行了预定的测试方案⑥测试时间不足
设有关系模式R(A1,A2,A3,A4,A5,A6),其中:函数依赖集F={A1→A2,A1A3→A4,A5A6→A1,A2A5→A6,A3A5→A6),则___________(21)是关系模式R的一个主键,R规范化程度最高达到____________(
在分布式数据库中有分片透明、复制透明、位置透明和逻辑透明等基本概念,其中:___________(19)是指局部数据模型透明,即用户或应用程序无须知道局部使用的是哪种数据模型;___________(20)是指用户或应用程序不需要知道逻辑上访问的表具体是怎
设系统中有R类资源m个,现有n个进程互斥使用。若每个进程对R资源的最大需求为w,那么当m、n、w取下表的值时,对于下表中的a~e五种情况,(26)两种情况可能会发生死锁。对于这两种情况,若将(27),则不会发生死锁。
软件测试的基本方法包括白盒测试和黑盒测试方法,以下关于二者之间关联的叙述,错误的是(61)。
假设系统中有三类互斥资源R1、R2和R3,可用资源数分别为10、5和3。在T0时刻系统中有P1、P2、P3、P4和P5五个进程,这些进程对资源的最大需求量和已分配资源数如下表所示,此时系统剩余的可用资源数分别为(22)。如果进程按(23)序列执行,那么系统
某企业生产流水线M共有两位生产者,生产者甲不断地将其工序上加工的半成品放入半成品箱,生产者乙从半成品箱取出继续加工。假设半成品箱可存放n件半成品,采用PV操作实现生产者甲和生产者乙的同步可以设置三个信号量S、S1和S2,其同步模型如下图所示。 信号量
关于软件著作权产生的时间,下面表述正确的是(10)。
随机试题
目前在WTO存在的单独关税区有()
Thisbirdisreallylovely,andI’veneverseen________one.
下列选项中不属于捕食的一项是()
土石坝施工中,当黏性土料含水量偏低时,主要应在()加水。
路基填土不得使用()等。
上个世纪60年代初以来,新加坡的人均预期寿命不断上升,到本世纪已超过日本,成为世界之最。与此同时,和一切发达国家一样,由于饮食中的高脂肪含量,新加坡人的心血管疾病发病率也逐年上升。从上述判定,最可能推出以下哪项结论?()
疼:哭
关于SDR,下列说法正确的是()。[南京大学2012金融硕士]
在"用户表"中有4个字段:用户名(文本型,主关键字),密码(文本型),登录次数(数字型),最近登录时间(日期/时间型)。在"登录界面"的窗体中有两个名为tUser和tPassword的文本框,一个登录按钮 Command0。进入登录界面后,用户输入用户名和
Somepeople’searsproducewaxlikebusylittlebees.Thiscanbeaproblemeventhoughearwax(耳垢)appearsto【S1】______animporta
最新回复
(
0
)