首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和图,填补流程图中的空缺。 【说明】 某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和e1表示底盘分别进入装配线0和
阅读以下说明和图,填补流程图中的空缺。 【说明】 某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和e1表示底盘分别进入装配线0和
admin
2008-04-04
50
问题
阅读以下说明和图,填补流程图中的空缺。
【说明】
某汽车制造工厂有两条装配线。汽车装配过程如图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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
从数据库管理系统的角度看,数据库系统一般采用如下图所示的三级模式结构。图中①②处应填写(26),③处应填写(27)。
下列设备和技术中,(65)不属于数据安全策略范畴。
为验证某呼叫中心是否能够承受大量呼叫信息同时呼入并得到正确处理,测试工程师一般采用______测试工具。A.负载压力B.代码C.网络仿真D.故障诊断
以下关于白盒测试和黑盒测试的理解,正确是______。A.白盒测试通过对程序内部结构的分析、检测来寻找问题B.白盒测试通过一些表征性的现象、事件、标志来判断内部的运行状态C.单元测试可应用白盒测试方法,集成测试则采用黑盒测试方法D.在软件生命周期各
若二维数组arr[1..M,1..N]的首地址为base,数组元素按列存储且每个元素占用K个存储单元,则元素arr[i,j]在该数组空间的地址为______。
假设段页式存储管理系统中的地址结构如下图所示,则系统()。
软件测试的基本方法包括白盒测试和黑盒测试方法,以下关于二者之间关联的叙述,错误的是(61)。
若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n),且是稳定的(即如果待排序的序列中两个数据元素具有相同的值,在排序前后它们的相对位置不变),则可选择的排序方法是______。
完成下列命令行,对网络接口进行地址初始化配置。firewall(config)#ipaddressinside(1)(2)firewall(config)#ipaddressoutside(3)(4)管道命令的作用是允许数据流从
随机试题
下列哪种激素是神经激素
新生儿丹毒称:
依据占有人的意思为标准,可以将占有分为:
[2012年第005题]下列4个图形属拓扑同构的是:
1972年《中美上海公报》有关台湾的内容初稿中,美国方面表明:“认识到中华人民共和国和台湾政府都认为只有一个中国,台湾是中国的一部分,美国政府对这一立场不提出异议。”我方对此提出了异议。我方为什么对初稿中美方声明提出异议?()
在考生文件夹下打开EXCEL.XLSX文件:选取“产品型号”列、“上月销售量”列和“本月销售量”列内容,建立“簇状柱形图”,图表标题为“销售情况统计图”,图例置底部;将图表插入到表的A14:E27单元格区域内,保存EXCEL.XLSX文件。
Therearevariouswaysinwhichindividualeconomicunitscaninteractwithoneanother.Threebasicwaysmaybedescribedasma
【B1】【B3】
每个人一生中都该有个志向,否则他的精力便会浪费掉。每个青年人都力求成为一个有成就的人物。一个青年人只期望富有是不明智的,或只专心于求得权利与名望也是不对的。一个:青年人希望做个有成就者,结果常常会实现。狄斯拉里(Disraeli)的故事是个例证。狄斯拉里开
Completethenotesbelow.WriteNOMORETHANTWOWORDSforeachanswer.KeepingKidsSafeontheInternetInternetforc
最新回复
(
0
)