首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间
admin
2013-07-09
43
问题
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。
【说明】
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为a
i
和b
i
。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业,而且作业处理是不可中断的,每个作业只能被处理一次。现要找出一个最优调度方案,使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
算法步骤:
(1)确定候选解上界为R段的单台处理机处理所有作业的完成时间m:
(2)用p(x,y,k)=1表示前志个作业可以在A用时不超过z且在B用时不超过y时间内处理完成,则p(x,y,k)=p(x一a
k
,y,k一1)||p(x,y一b
k
,k一1)(||表示逻辑或操作)。
(3)得到最短处理时间为min(max(z,y))。
【C代码】
下面是该算法的C语言实现。
(1)常量和变量说明
n:作业数
m:候选解上界
n:数组,长度为n,记录n个作业在A上的处理时间,下标从0开始
b:数组,长度为n,记录n个作业在B上的处理时间,下标从0开始
k:循环变量
p:三维数组,长度为(m+1)*(m+1)*(n+1)
temp:临时变量
max:最短处理时间
(2)C代码
#include
int n,m;
int a[60],b[60],p[100][100][60];
void read(){/*输入n、a、b,求出m,代码略*/)
void schedule(){/*求解过程*/
int X,y,k;
for(x=0;x<=m;x++){
for(y=0;y<m;y++){
(1)
for(k=1;k
p[x][y][k]=0;
}
}
for(k=1;k<n;k++){
for(x=0;x<=m;x++){
for(y=0;y<=m;y++){
if(x-a[k-1]>=0)
(2)
;
if(
(3)
)p[x][y][k]=(p[x][y][k]|| p[x][y-b[k-1]][k-1]);
}
}
}
}
void write(){/*确定最优解并输出*/
int X,y,temp,max=m;
for(x=0;x<=m;x++){
for(y=0;y<=m;y++){
if(
(4)
){
temp=
(5)
;
if(temp<max)max=temp;
}
}
}
printf(“\n%d\n”,max);
}
void main(){read();schedule();write();}
根据以上说明和C代码,填充C代码中的空(1)~(5)。
选项
答案
(1)p[x][y][0]=1 (2)pEx][y][k]=p[x-a[k-1]][y][k-1] (3)y-b[k一1]>=0 (4)p[x][y][n]==1或pEx][y][n]或pEx]Ey][n]!=0 (5)(x>=y)?x:Y
解析
从schedtue()函数的第一个程序段可以看出,该段程序主要进行初始化第一个作业,下标以0开始,即p[x][y][0]=1,内层循环里的pLx][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处理,因此判定条件应为y—b[k一1]>=0。 write()程序段用于确定最优解并输出结果,即得到最短处理时间min(max(x,y))。(4)的判定条件是任务n完成,因此为p[x][y][n]=一1或其等价形式。(5)为表达max(x,y),为(x>=y)?x:y。
转载请注明原文地址:https://kaotiyun.com/show/hiDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
已知关系模式:图书(图书编号,图书类型,图书名称,作者,出版社,出版日期,ISBN),图书编号唯一识别一本图书。建立“计算机”类图书的视图Compute-BOOK,并要求进行修改、插入操作时保证该视图只有计算机类的图书。CREATE(1)
结构化分析(StructuredAnalysis,SA)是面向数据流的需求分析方法,______不属于SA工具。A.分层的数据流图B.数据词典C.问题分析图D.描述加工逻辑的结构化语言、判定表或判定树
若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n),且是稳定的(即如果待排序的序列中两个数据元素具有相同的值,在排序前后它们的相对位置不变),则可选择的排序方法是______。
某校园网用户无法访问外部站点210.102.58.74,管理人员在Windows操作系统下可以使用(30)判断故障发生在校园网内还是校园网外。
下图是责任链设计模式的类图,该设计模式的目的是________。该图中,Handler和Handler之间是关联关系,Handler和ConcreteHandler之间是继承关系。
某开发小组为某企业开发较大规模的项目,该开发小组已经为同一行业的其他企业开发过类似的项目,且该项目需求变化很少,则最适宜采用_______开发过程模型。
以下关于数据流图的基本要素的叙述中,不正确的是_______。
在C程序中,________是合法的用户定义变量名。①123②form-7③short④form7
目前,通过移动电话接人互联网采用的主要技术是什么?公司网络中的设备或系统(包括存储商业机密的数据库服务器、邮件服务器、存储资源代码的PC机、应用网关、存储私人信息的PC机、电子商务系统)哪些应放在DMZ中,哪些应放在内网中?给予简要说明。
阅读以下说明,回答问题1至问题5。[说明]某企业采用Windows2000操作系统部署企业虚拟专用网(VPN),将企业的两个异地网络通过公共Internet安全地互联起来。微软Windows2000操作系统当中对IPSec具备完善的支持,下图
随机试题
X线在真空中传播时,X线量的衰减与传播距离的关系是
某公路工程采用招标代理方式进行施工招标。在招标与施工阶段发生了如下事件:事件1:招标代理机构提出,评标委员会由7人组成,包括建设单位纪委书记、工会主席,当地招标投标管理办公室主任,以及从交通运输主管部门建立的评标专家库中随机抽取的4位技术、经济专
A公司将两辆大型运输车辆与B公司的一台生产设备相交换,另支付补价10万元。在交换日,A公司用于交换的两辆运输车辆账面原价为140万元,累计折旧为25万元,公允价值为130万元;B公司用于交换的生产设备账面原价为300万元,累计折旧为175万元,公允价值为1
卧薪尝胆:勾践
贫困常常使人想到低矮的土房、破旧的被褥、浑浊的双眼。这的确是生活在城市最低生活标准线下的贫困人家。男人病逝,欠下很多钱,两个孩子一个有点残疾,但他们家窗明几净,有冰箱、洗衣机,有漂亮的窗帘和门帘。女主人的笑容就像她的屋子一样明朗,她说,冰箱、洗衣机都是邻居
印象管理是指人试图控制他人对自己形成的印象的过程。一个人留给他人的印象表明了他人对其的知觉、评价,甚至会使他人形成对其的特定应对方式。因而,为了给他人留下好的印象,得到他人好的评价与对待,人会用一种给他人造成特定印象的方式来自我表现。印象管理的运用,尤其要
人权是人作为人所享有或应当享有的权利。法律的重要使命就是充分尊重和保障人权,不得以任何借口侵犯人权。人权的法律保障包括()
数据库系统的核心是
在使用基于优先数的不可抢占式进程调度算法的系统中,不会引起进程切换的事件恳()。
A、 B、 C、 B题目为询问为什么员工感到难以按照说明进行操作的Why疑问句。
最新回复
(
0
)