首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和流程图,请将流程图中(1)~(5)空缺处的内容填补完整。 [说明] 某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和
阅读下列算法说明和流程图,请将流程图中(1)~(5)空缺处的内容填补完整。 [说明] 某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。 (1)e0和
admin
2010-01-15
47
问题
阅读下列算法说明和流程图,请将流程图中(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://jikaoti.com/ti/5oi7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在面向对象分析和设计中,用类图给出系统的静态设计视图,其应用场合不包括___________(45)。下图是一个UMI,类图,其中类University和类School之间是___________(46)关系,类Person和类PersonRecord之间
在面向对象分析和设计中,用类图给出系统的静态设计视图,其应用场合不包括___________(45)。下图是一个UMI,类图,其中类University和类School之间是___________(46)关系,类Person和类PersonRecord之间
在分布式数据库中有分片透明、复制透明、位置透明和逻辑透明等基本概念,其中:___________(19)是指局部数据模型透明,即用户或应用程序无须知道局部使用的是哪种数据模型;___________(20)是指用户或应用程序不需要知道逻辑上访问的表具体是怎
()不属于程序的基本控制结构。
计算机的用途不同,对其部件的性能指标要求也有所不同。以科学计算为主的计算机,对(1)要求较高,而且应该重点考虑(2)。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则里程碑(33)在关键路径上。活动GH的松弛时间是(34)。(33)
数据库系统通常采用三级模式结构:外模式、模式和内模式。这三级模式分别对应数据库的__________。
对高级语言源程序进行编译时,可发现源程序中的(21)错误。
对于下面的有向图,其邻接矩阵是一个①的矩阵。采用邻接链表存储时,顶点0的表结点个数为2,顶点3的表结点个数为0,顶点1的表结点个数为②个。②处应填入?
编译和解释是实现高级程序设计语言的两种方式,其区别主要在于______。
随机试题
简述幼儿再造想象的主要特点。
狭义的工程险主要包括()。
导致企业财产物资账存数与实存数不符的主要原因有()。
个人住房装修贷款的贷款对象应满足的条件不包括()
四川道琴又称“竹琴”,俗称“隔壁戏”,一般由一人扮演多个角色。()
下列哪一选项是蚊子用于获取“猎物”信息的主要器官:()
从所给四个选项中,选择最合适的填入1和2处,使之呈现一定的规律性:
1911年,美国工程师()出版《科学管理原理》一书,奠定了科学管理的理论基础,被誉为“科学管理之父”。
A、节日B、周末C、春节A
Howmanythingsarenecessarytolearnforeignlanguages?
最新回复
(
0
)