2. 计算机
  3. 阅读下列说明C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一

阅读下列说明C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一

admin2014-11-13  105
问题 阅读下列说明C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
算法步骤：
(1)确定候选解上界为最短的单台处理机处理所有作业的完成时间m，

(2)用p(x，y，k)=1表示前k个作业可以在A用时不超过x且在B用时不超过y时间内处理完成，则p(x，y，k)=p(x—ak，Y，k一1)∥p(x，y．bk，k一1)(11表示逻辑或操作)。
(3)得到最短处理时间为min(max(x，y))。
【C代码】
下面是该算法的C语言实现。
(1)常量和变量说明
n：作业数
m：候选解上界
a：数组，长度为n，记录n个作业在A上的处理时间，下标从0开始
b：数组，长度为n，记录n个作业在B上的处理时间，下标从0开始
k：循环变量
p：三维数组，长度为(m+1)*(m+1)*(n+1)
temp：临时变量
max：最短处理时间
(2)C代码
#include
intn，m；
inta[60]，b[60]，P[100][100][60]；
voidread()(／*输入rl、a、b，求出m，代码略*／)
voidschedule()(／(求解过程*／
intX，Y，k；
for(x=0；x<=m；x++){
for(y=0；y(1)
for(k=1；kP[x][y][k]=0；
}
}
for(k=1；kfor(x=0；x<=m；x++){
for(y=0；y<=m；y++){
if(x—a[k一1]>=0)(2)；
if((3))p[x][y][k]=(pIx][y][k]lIP[X][y—b[k一1]][k一1])；
}
}
}
}
voidwrite(){／*确定最优解并输出*／
intXY，temp,max：m；
for(x=0；x<=m；x++){
for(y=0；y<=m；y++){
if((4)){
temp=(5)；
if(temp}
}
}
printf(“＼n％d＼n”，max)；
}
voidmain()(read()；schedule()；write()；)
考虑6个作业的实例，各个作业在两台处理机上的处理时间如表15一1所示。该实例的最优解为(7)，最优解的值(即最短处理时间)为(8)。最优解用(x1，x2，x3，x4，x5，x6)表示，其中若第i个作业在A上处理，则xi=1，否则xi=2。如(1，1，1，1，2，2)表示作业1，2，3和4在A上处理，作业5和6在B上处理。
选项
答案(7)(1，1，2，2，1，1)(8)15
解析 为了方便考生更好地理解本算法的思想，现做如下分析：当完成k个作业，设机器A花费了x时间，机器B所花费时间的最小值肯定是x的一个函数，设F[k][x]表示机器B所花费时间的最小值，则F[k][x]=Min{F[k—1][x]+b[k]，F[k．1][x—a[k]]}。其中F[k—1][x]+b[k]表示第k个作业由机器B来处理(完成k-1个作业时机器A花费的时间仍是x)，F[k—1][x．a[k]]表示第k个作业由机器A处理(完成k—1个作业时机器A花费的时间是x-a[k])。那么单个点对较大值max(x，F[k][x])，表示此时(即机器A花费X时间的情况下)所需要的总时间。而机器A花费的时间x是变化的，即x=0，1，2…x(max)，由此构成了点对较大值序列。要求整体时间最短，取这些点对较大值序列中最小的即是。现分析前两个作业的情况：对于第一个作业：下标以0开始。首先，机器A所花费时间的所有可能值范围：0<=x<=a[0]。设x<0时，设F[0][x]=∞，则max(x，∞)=∞。记法意义见下。x=0时，F[0][01=3，则max(0，3)=3，机器A花费0时间，机器B花费3时间，而此时两个机器所需时间为3；x=1时，F[0][1]=3，max(1，3)=3；x=2时，F[0][2]=0，则max(2，0)=2；那么上面的点对序列中，可以看出当x=2时，完成第一个作业两台机器花费最少的时间为2，此时机器A花费2时间，机器B花费0时间。再来看第二个作业。首先，x的取值范围是：0<=X<=(a[0]+a[11)。当x<0时，记F[1][x]=∞。这个记法编程使用，因为数组下标不能小于0。在这里的实际含义是：x是代表完成前两个作业机器A的时间，a[1l是机器A完成第2个作业的时间，若xx=0，NF[1][0]=min{F[0][0]+b[21，F[0][0—a11]1)=min{3+8，∞)=11，进而max(0，11)=11；
x=l，则F[1][1]=min{F[0][1]+b[2]，F[0][1—a[1]]}=min{3+8，∞}=11，进而max(11)=11；
x=2，则F[I][21=min{F[0][2]+b[2]，F[0][2一a[11]}=min{0+8，∞}=8，进而max(2，8)=8；
x=3，则F[1][3]=min{F[0][3]+b[2]，F[0][3一a11]])=min{0+8，∞)=8，进而max(3，8)=8；
x=4，则F[1][4]=min{F[0114]+b[2]，F[0114一a[1]])=min{0+8，∞}=8，进而max(4，8)=8；
x=5，则F[1][5]=min{F[0][5]+b[2]，F[0][5一a[1]]}=min{0+8，3}=3，进而max(5，3)=5；
x=6，则F[11161=min{F[0l[6]+b[21，F[0][6一a[1]]}=min{0+8，3l=3，进而max(6，3)=6：
x=7，则F[1l[71=min{F[0l[7]+b[21，F[0][7一a[1]}=min{0+8，0)=0，进而max(7，0)=7；
那么上面的点对序列中，可以看出当x=5时，完成两个作业两台机器花费最少的时间为5，此时机器A花费5时间，机器B花费3时间。接下来依次类推即可，最终该实例的最优解为(1，1，2，2，1，1)，最短处理时间为15。这里提供当各个作业完成时的最短处理时间，考生可自行推导：2，5，7，12，14，15。
转载请注明原文地址:https://kaotiyun.com/show/EpDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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