首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和流程图,请将流程图中(1)~(5)空缺处的内容填补完整。 [说明] 某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和
阅读下列算法说明和流程图,请将流程图中(1)~(5)空缺处的内容填补完整。 [说明] 某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和
admin
2010-01-15
37
问题
阅读下列算法说明和流程图,请将流程图中(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
有关评估系统效率质量特性,以下论述正确的是______。A.响应时间越长,系统执行效率越高B.响应时间和交易执行吞吐量都是用来衡量系统执行快慢的C.响应时间越短,交易执行吞吐量越大D.系统的访问量越大,交易执行吞吐量越大
软件工程每一个阶段结束前,应该着重对可维护性进行复审。在系统设计阶段的复审期间,应该从(8)出发;评价软件的结构和过程。
下图为某设计模式的类图,类State和Context的关系为(49),类(50)是客户使用的主要接口。(50)
在各种不同的软件需求中,(36)描述了用户使用产品必须要完成的任务,可以用UML建模语言的(37)表示。(37)
如果主存容量为16M字节,且按字节编址,表示该主存地址至少应需要(3)位。
以下测试内容中,属于系统测试的是()。①单元测试②集成测试③安全性测试④可靠性测试⑤兼容性测试⑥可用性测试
关于汇编语言,以下叙述中正确的是(20)。
ICMP协议属于因特网中的(27)协议,ICMP协议数据单元封装在(28)中传送。(28)
以下关于软件测试原则的叙述中,正确的是______。①所有软件测试都应追溯到用户需求②尽早地和不断地进行软件测试③完全测试是不可能的④测试无法发现软件潜在的缺陷⑤需要充分注意测试中的群集现象
某模块内涉及多个功能,这些功能必须以特定的次序执行,则该模块的内聚类型为______内聚。
随机试题
关于控制钢筋伸长率的说法,正确的是()。
A.主动脉B.微动脉C.毛细血管D.微静脉血流速度最快的是()
脉结代,心动悸,虚羸少气,舌光少苔,治宜选用
宪法修改的方式主要包括()
某大桥主跨为20×40m预应力混凝土简支T梁桥,合同总价为18700万元,合同工期2年。大桥桥址处地质条件如下:原地面往下依次为黏土、砂砾石、泥岩,主墩基础为直径2.0m的钻孔灌注桩,设计深度为40m,采用回转钻进施工法钻孔,导管法灌注水下混凝土。T梁施工
实验是进行科学探究的重要方式,请根据下图回答问题:A.水通直流电B.测定空气中氧气含量C.二氧化碳性质实验D.细铁丝在氧气中燃烧用A图所示装置进行电解水实验时,a管产生的气体是______。
A、 B、 C、 D、 A图形中的交点数均为7。故本题选A。
A、 B、 C、 D、 B
假定在窗体上建立一个通用对话框,其名称为CommonDialog1,用下面的语句可以建立一个对话框:CommonDialog1.Action=4与该语句等价的语句是()。
Inthequesttofinda__________forcancer,scientistsmustdrawonacollectiveinformationbase.
最新回复
(
0
)