首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
82
问题
阅读下列说明和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代码,算法的时间复杂度为
(6)
(用O符号表示)。
选项
答案
(6)O(m2n)
解析
从程序的循环层数即可看出算法的时间复杂度。程序的最高循环层数为3层。最外层循环变量的变化范围是1~n一1,次外层循环变量的变化范围是0~m,内层循环变量的变化范围是0~m,所以时间复杂度为0(m
2
n)。
转载请注明原文地址:https://kaotiyun.com/show/miDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在引入自动化测试工具以前,手工测试遇到的问题包括()。①工作量和时间耗费过于庞大②衡量软件测试工作进展困难③长时间运行的可靠性测试问题④对并发用户进行模拟的问题⑤确定系统的性能瓶颈问题⑥软件测试过程的管
若浮点数的阶码用移码表示,尾数用补码表示。两规格化浮点数相乘,最后对结果规格化时,右规的右移位数最多为(2)位。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的权重表示活动的持续时间(天),则里程碑C在关键路径上。在其他活动按时完成的情况下,活动FJ最多可以晚_______天开始而不影响工期。
给出关系R(A,B,C)和S(A,B,C),R和S的函数依赖集F={A→B,B→C}。若R和S进行自然连接运算,则结果集有3个属性。关系R和S________。
通常VLAN有静态和动态2种实现方式,这2种方式分别是如何实现的?各有什么特点?Switch1采用的是哪种实现方式?填充VLAN信息表如表9-3所示,将答案填写在答题纸相应位置。
阅读以下说明,回答问题1至问题4,将解答填人答题纸的对应栏内。[说明]某小公司的网络拓扑如图9-2所示。其中路由器具有ISDN模块,公司网络通过ISDN连接到ISP。
从下列选项中选取合适的答案分别填入图4-1中的(1)~(4)处。A.DES算法B.MD5算法C.会话密钥D.数字证书E.甲的公钥F.甲的私钥G.乙的公钥H.乙的私钥当乙收到了地
根据图3-1所给出的网络连接方式及相关的网络参数,区域(A)与区域(B)中计算机的网络参数配置(如图3-2所示)为:区域(A)计算机“IP地址”(范围):(1):区域(A)计算机“子网掩码”;(2);区域(A)计算机“默认网关”:(
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
随机试题
有关零增长模型,下列说法正确的是()。
下面关于可待因的说法错误的是
患者,女,30岁。1周来发热、尿频、尿急、尿痛伴腰痛,既往无类似病史。查体:体温38.3℃,心肺检查未见异常,腹软,肝脾肋下未触及,双肾区有叩击痛。化验:尿蛋白(+),白细胞30~50/Hp,可见白细胞管型。对该患者最可能的诊断是
《公路工程技术标准》属于哪一类标准?()
政府采购的原则包括()。
某施工单位在一个多雨季节开展户外施工,在做进度计划时项目经理将天气因素纳入项目活动依赖关系之中,制订了项目活动计划,本项目中,项目经理采用______________技术,确定项目各活动中的依赖关系。
A、Inapostoffice.B、Ataninsurancecompany.C、Onanairplane.D、Inamoviecompany.A本题考查对对话发生地点的判断。关键词为package(包裹)和send...by
TheAsianEconomicCrisisOverthelastseveralmonths,theeconomicnewshasbeendominatedbythecrisisinEastAsia—unco
HowPsychologyCanHelpthePlanetStayCool[A]"I’mnotconvincedit’sasbadastheexpertsmakeout...It’severyoneelse’sf
A、Declininghealth.B、Lackofattention.C、Lossofmotivation.D、Improperbehavior.B
最新回复
(
0
)