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

admin2014-11-13  32

问题 阅读下列说明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();)
根据以上说明和C代码,填允C代码中的空(1)~(5)。

选项

答案(1)p[x][y][0]=1(2)p[x][y][k]=p[x—a[k—1]][y][k—1](3)y-b[k一11>=0 (4)p[x][y][n]=1,或p[x][y][n]或p[x][y][n]!=0(5)(x>=y)?x:y

解析 从schedule()函数的第一个程序段可以看出,该段程序主要进行初始化第一个作业,下标以0开始,即p[x][y][0]=1,内层循环里的p[x][y][k]=0用于初始化后面的n-1个作业。第二个程序段是对后面的n—1个作业,确定。p(x,y,k)的值。x.a[k.1]>=0的判定条件若成立,则表示第k个作业由机器A处理,完成k一1个作业时机器A花费的时间是x—a[k—1],即p[x][y][k]=p[x—a[k—1][y][k—1]。(3)空要求填入一判定条件,由其后的执行语句可知,第k个作业由机器B
转载请注明原文地址:https://kaotiyun.com/show/IpDZ777K
0

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