2. 计算机
  3. 阅读下列算法说明和流程图，请将流程图中(1)～(5)空缺处的内容填补完整。 [说明] 某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示，即汽车底盘进入装配线，零件在多个工位装配，结束时汽车自动完成下线工作。 (1)e0和

阅读下列算法说明和流程图，请将流程图中(1)～(5)空缺处的内容填补完整。 [说明] 某汽车制造工厂有两条装配线。汽车装配过程如图4-16所示，即汽车底盘进入装配线，零件在多个工位装配，结束时汽车自动完成下线工作。 (1)e0和

admin2010-01-15  85
问题 阅读下列算法说明和流程图，请将流程图中(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://kaotiyun.com/show/60DZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)