首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和图,填补流程图中的空缺。 【说明】 某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和e1表示底盘分别进入装配线0和
阅读以下说明和图,填补流程图中的空缺。 【说明】 某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和e1表示底盘分别进入装配线0和
admin
2008-04-04
49
问题
阅读以下说明和图,填补流程图中的空缺。
【说明】
某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。
(1)e0和e1表示底盘分别进入装配线0和装配线1所需要的时间。
(2)每条装配线有n个工位,第一条装配线的工位为S0,0,S0,1,…,S0,n-0,第二条装配线的工位为S1,0,S1,1,…,S1,n-1。其中S0,k和S1,k(0≤k≤n-1)完成相同的任务,但所需时间可能不同。
(3)aij表示在工位Sij处的装配时间,其中i表示装配线(i=0或i=1),j表示工位号(0≤j≤n-1)。
(4)tij表示从Sij处装配完成后转移到另一条装配线下一个工位的时间。
(5)X0和X1表示装配结束后,汽车分别从装配线0和装配线1下线所需要的时间。
(6)在同一条装配线上,底盘从一个工位转移到其下一个工位的时间可以忽略不计。
图10-7所示的流程图描述了求最短装配时间的算法,该算法的输入为;
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处的最短装配时间。
选项
答案
(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)f[j][j-1)+a[1][j]<f[0][j-1)+t[0][j-1]+a[1][j], 或f[1][j-1)+a[1][j]<=f[0][j-1]+t[0][j-1)+a[1][j], 或其等价形式 (4)fi=f[0][n-1]+x[0] li=0 (5)fi=f[1][n-1]+x[1] 1i=1
解析
本题考查动态规划算法设计方法。
当问题具有两个特性,即最优子结构和重叠子问题时,可以考虑用动态规划求解问题。用动态规划求解问题具有四个步骤。
(1)刻画问题的最优子结构,描述问题的最优解包含子问题的最优解。对于本题来说,最短装配时间等于经过装配线。的第n个工位的最短装配时间加上x[0],或者等于经过装配线1的第n个工位的最短装配时间加上x[1],取哪条装配线取决于哪个值更小。而经过某个装配线0/1的第i个工位的最短装配时间又等于经过装配线0/1的第1-1个工位的最短装配时间,或者等于经过装配线I/0的第i-1个工位的最短装配时间加上从这个工位到装配线0/1的迁移时间,取决于哪个值更小。
(2)建立最优子结构的递归关系,这是非常关键的一步。对于本题来说,递归关系为
(3)根据递归关系求最优解的值。对于本题来说,最优解记录在fi中,fi= min(f(0,n-1)+x0,f(1,n-1)+x1):
(4)构造最优解。对于本题来说,只是求出最优解是从哪条装配线装配出来,并没有记录最优解。
转载请注明原文地址:https://kaotiyun.com/show/ufDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
(61)方法根据输出对输入的依赖关系设计测试用例。
某供应商数据库中的供应关系为SPJ(供应商号,零件号,工担号,数量),如下命令查询某工程至少用了3家供应商(包含3家)供应的零件的平均数量,并按工程号的降序排列。SELECT工程号,(14)FROMSPJGROUPBY工程号(15)
GB/T16260将软件的内部(外部)质量属性划分为六大质量特性,分别是(65)。
以下各项中,(51)属于需求说明书的评测内容。①系统定义的目标是否与用户的要求一致②设计的约束条件或限制条件是否符合实际③是否考虑过软件需求的其他方案④软件的行为与它必须处理的信息、必须完成的功能是否一致
设有职工EMP(职工号,姓名,性别,部门号,职务,进单位时间,电话),职务JOB(职务,月薪)和部门DEPT(部门号,部门名称,部门电话,负责人)实体集。一个职务可以由多个职工担任,但一个职工只能担任一个职务,并属于一个部门,部门负责人是一个职工。下图所示
针对下列程序段,需要(52)个测试用例才可以满足语句覆盖的要求。 switch(value){ case 0: other=30; break; case 1:
在执行测试和评价的过程中,会产生较多的文档,(43)是对文档内容的正确描述。①评价需求的主要内容是描述评价的目标,特别是描述了产品的质量需求。②评价规格说明的主要内容是确定对软件及其部件实行的所有分析和测量,标识要采用的操作规程、测试方法和工具。③评
对软件可靠性的理解,正确的是(45)。①软件可靠性是指在指定条件下使用时,软件产品维持规定的性能级别的能力②软件可靠性的种种局限是由于随着时间的推移,软件需求和使用方式发生了变化③软件可靠性包括成熟性、有效性、容错性、易恢复性
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(37)
某教学管理数据库中,学生、课程关系模式和主键分别为:S(学号,姓名,性别,家庭住址,电话),关系S的主键为学号;C(课程号,课程名,学分),关系C的主键为课程号。假设一个学生可以选择多门课程,一门课程可以由多个学生选择。一旦学生选择某门课程必定有该课程的成
随机试题
采用热疗法促进炎症局限的机制是
红绛舌的形成机理主要有
患者,女,36岁。脘腹痞闷,嘈杂,饥不欲食,恶心嗳气,口燥咽干,大便秘结,舌红少苔,脉细数。临床当治以
服药方法,汤剂都宜
经城市规划行政主管部门批准的建设用地范围的界线,称为()。
下列关于供给的价格弹性的说法中,正确的是()。
大卫体格健壮,神态坚定,左手轻推肩上的投石带,在投入战斗前的瞬间,他侧首______左前方,目光如炬。《大卫》象征着为正义事业而奋斗的力量,雕塑家在他身上______了自己炽烈的爱国主义理想。填入划横线部分最恰当的一项是:
2009年10月6日,诺贝尔奖评审委员会宣布,因对光纤通讯研究有重大贡献,香港中文大学前任校长、“光纤之父”(),与美国科学家史密斯和博伊尔分享2009年的诺贝尔物理学奖。
假定你是李明。伦敦银行(BankofLondon)的Williams先生即将结束为期一周的访问,请你帮助他安排回程,并据此写张便条留在他房间。内容要点:1.适当寒暄;2.将送他去机场,明早8点前台等候;3.要送他
【B1】【B9】
最新回复
(
0
)