首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和图,填补流程图中的空缺。 【说明】 某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和e1表示底盘分别进入装配线0和
阅读以下说明和图,填补流程图中的空缺。 【说明】 某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和e1表示底盘分别进入装配线0和
admin
2008-04-04
52
问题
阅读以下说明和图,填补流程图中的空缺。
【说明】
某汽车制造工厂有两条装配线。汽车装配过程如图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
软件设计师下午应用技术考试
软考中级
相关试题推荐
三个可靠度R均为0.8的部件串联构成一个系统,如下图所示:则该系统的可靠度为(7)。
多条件覆盖是一种逻辑覆盖,它的含义是设计足够的测试用例,使得每个判定中条件的各种可能组合都至少出现一次,满足多条件覆盖级别的测试用例也是满足(44)级别的;针对布尔表达式A&&(B‖C)执行逻辑覆盖测试,测试用例至少需要(45)种组合才能满足多条件覆盖的要
针对下面程序段,边界值问题可以定位在(62)1:RemCregea10elementintegerarray2:RemInitializeeachelementto-13:Dimdata(10)As
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
在面向对象的语言中,(7)。
以下关于软件系统安全防护策略的叙述,不正确的是______。A.网闸的主要目的是实现内网和外网的物理隔离B.防火墙的主要目的是实现内网和外网的逻辑隔离C.入侵检测系统通常部署在防火墙之外D.安全日志属于被动防护策略
以下关于软件生命周期的叙述不正确的是______。A.软件生命周期包括以下几个阶段:项目规划、需求定义和需求分析、软件设计、程序编码、软件测试、运行维护B.程序编码阶段是将软件设计的结果转换成计算机可运行的程序代码。为了保证程序的可读性、易维护性和提高
针对以下C语言程序段,假设sta[10]=-1,对于x的取值,需要______个测试用例能够满足分支覆盖的要求。intMathMine(intx){intm=0;inti;for(i=x-1;i<=x+1;
在面向对象技术中,(43)是一组具有相同结构、相同服务、共同关系和共同语义的(44)集合,其定义包括名称、属性和操作。(44)
若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n),且是稳定的(即如果待排序的序列中两个数据元素具有相同的值,在排序前后它们的相对位置不变),则可选择的排序方法是______。
随机试题
Ifyou’redrivinginBrooklyn,Ohio,andfindyourselfattractedbyyoursurroundings,resisttheurgetogetholdofyourcell
Canadaisthesecondlargestcountryintheworldinarea,althoughits【1】isonlysome25million,most【2】ina200-milestrip【3】
脑底动脉环在脑循环中起着非常重要的作用,能沟通脑前、后、左、右的血液供应,下列哪条动脉不参与脑底动脉环的组成
主治节是指
尼古拉兹实验曲线图中,在以下哪个区域里,不同相对粗糙度的试验点,分别落在一些与横轴平行的直线上,阻力系数λ与雷诺数无关?()
甲公司为一家上市公司,2013年对外投资有关资料如下:(1)1月20日,甲公司以银行存款购买A公司发行的股票200万元股作为可供出售金融资产,实际支付价款11000万元(含已宣告尚未发放的现金股利20万元),另支付相关税费10万元,占A公司有表决
某公司对某仪器的尺寸测量如图5.5—4所示,为测量尺寸lB,先采用卡尺测得尺寸lA和尺寸lC分别为29.95mm和16.52mm,而lB=lA—lC=13.43mm。设包含因子k=3,则尺寸lB的扩展不确定度U=()。
下列文种中,行文方向固定的是()。
山洪中学、华师附中、仁达附中、交大附中这四所中学每所有两支足球队,这8支足球队的队长分别为A、B、C、D、E、F、G、H(不按顺序)。近期,这四所学校的8支球队将联合举办一系列友谊赛。赛事规定本校的两只球队互相不比赛,任两个队(除同个学校的两个队外)
(1):考生文件火下有一个上程文件sjt3.vbp。程序的功能是:通过键盘向文本框中输入数字,如果输入的是非数字字符,则提示输入错误,且文本框中不显示输入的字符。单击名称为Command1、标题为“添加”的命令按钮,则将文本框中的数字添加到名称为Cnmbb
最新回复
(
0
)