首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和图,填补流程图中的空缺。 【说明】 某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和e1表示底盘分别进入装配线0和
阅读以下说明和图,填补流程图中的空缺。 【说明】 某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和e1表示底盘分别进入装配线0和
admin
2008-04-04
48
问题
阅读以下说明和图,填补流程图中的空缺。
【说明】
某汽车制造工厂有两条装配线。汽车装配过程如图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
软件设计师下午应用技术考试
软考中级
相关试题推荐
多条件覆盖是一种逻辑覆盖,它的含义是设计足够的测试用例,使得每个判定中条件的各种可能组合都至少出现一次,满足多条件覆盖级别的测试用例也是满足(44)级别的;针对布尔表达式A&&(B‖C)执行逻辑覆盖测试,测试用例至少需要(45)种组合才能满足多条件覆盖的要
为了解决进程间的同步和互斥问题,通常采用一种称为(21)机制的方法。若系统中有5个进程共享若干个资源R,每个进程都需要4个资源R,那么使系统不发生死锁的资源R的最少数目是(22)。
在UNIX操作系统中,把输入/输出设备看作是(23)。
负载压力性能测试需求分析时,应该选择(63)类型的业务作为测试案例。 ①高吞吐量的业务 ②业务逻辑复杂的业务 ③高商业风险的业务 ④高服务器负载的业务 ⑤批处理的业务
内存按字节编址,地址从90000H到CFFFFH,若用存储容量为16KB×8bit的存储器芯片构成该内存,至少需要(3)片。
软件测试原则中指出“完全测试是不可能的”,主要原因是______。A.输入量太大、输出结果太多以及路径组合太多B.自动化测试技术不够完善C.测试的时间和人员有限D.仅仅靠黑盒测试不能达到完全测试
如果在程序中的多个地方需要使用同一个常数,那么最好将其定义为一个符号常量,这样______。
在结构化分析方法中,利用分层数据流图对系统功能建模。以下关于分层数据流图的叙述中,不正确的是___________(32)。采用数据字典为数据流图中的每个数据流、文件、加工以及组成数据流或文件的数据项进行说明,其条目不包括____________(33)。
在分布式数据库中有分片透明、复制透明、位置透明和逻辑透明等基本概念,其中:___________(19)是指局部数据模型透明,即用户或应用程序无须知道局部使用的是哪种数据模型;___________(20)是指用户或应用程序不需要知道逻辑上访问的表具体是怎
随机试题
A.散发性发病B.小流行C.流行D.大流行E.暴发流行传染病病例发病时间的分布高峰集中于一个短时间之内者称为()
初孕妇,34周孕,既往有再生障碍性贫血病史,现血红蛋白为50g/L,血小板45×109/L,应采取的措施是
碳酸氢钠溶液煮沸灭菌时,其煮沸时间一般为
患者已确诊为骨巨细胞瘤,局部皮肤表浅静脉怒张,肿胀与压痛均显著,触诊有乒乓球样感觉。X片:骨皮质已破坏,断裂。病理报告:骨巨细胞瘤Ⅲ级。治疗应选择()
下列选项中,不属于合理经济规模衡量指标的是()。
砖基础墙的防潮层位置宜在室内地面标高()处。
税务机关欠税清缴制度包括()。
ItisonOctober1,2009thatthePeoplesRepublicofChina_______its60thbirthday.
公文如有附件,按顺序应当注明附件的()。
简述乔姆斯基的转换生成语法理论。
最新回复
(
0
)