首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
26
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
黑盒测试法是根据产品的______来设计测试用例的。A.功能B.输入数据C.应用范围D.内部逻辑
在网络应用测试中,网络延迟是一个重要指标。以下关于网络延迟的理解,正确的是(64)
下图是________________设计模式的类图,该设计模式的目的是________________,图中,Decorator和Component之间是________________关系,ConcreteDecorator和Decorator之间是_
能够主动采集信息,分析网络攻击行为和误操作的实时保护策略是指(64)。
下列操作系统中,_____保持网络系统的全部功能,并具有透明性、可靠性和高性能等特性。
以下______不属于单元测试中模块接口测试的测试内容。
下图是责任链设计模式的类图,该设计模式的目的是________。该图中,Handler和Handler之间是关联关系,Handler和ConcreteHandler之间是继承关系。
在C程序中,对于如下的两个for语句,其运行后a和b的值分别为________。for(inta=0;a=0,a++);for(intb=0;b=0;++b);
SSL协议使用(1)密钥体制进行密钥协商。在IIS5.0中,Web服务器管理员必须首先安装Web站点数字证书,然后Web服务器才能支持SSL会话,数字证书的格式遵循ITU-T(2)标准。通常情况下,数字证书需要由(3)颁发。如果Web服务器管理员准备预
FTTx+LAN接入方式采用什么拓扑结构?将图中(1)~(3)处空缺的传输介质名称填写到答题纸的相应位置。
随机试题
假如地球重力加速度减为现在的一半,下列数值不会发生变化的是()。
元件的类型有几种()
妊娠39周,初产妇,24岁,规律宫缩12小时,宫口开大3cm,破膜12小时,先露S-3,估计胎儿体重3000g,胎心128次/分,骨盆测量骶耻外径17cm,坐骨结节间径8cm:
患者,男性,76岁。因近日上呼吸道感染诱发慢性阻塞性肺疾病发作入院,医嘱给予抗感染、平喘、祛痰治疗,输液总量为800ml,计划5小时输完,输液器滴系数为15,每分钟滴数为()
《特种设备安全监察条例》规定,()的制造、安装、改造、重大维修过程,必须经国务院特种设备安全监督管理部门核准的检验检测机构按照安全技术规范的要求进行监督检验,未经监督检验合格的不得出厂或者交付使用。
下列各项中,属于企业所得税规定的不征税收入的是()。
转登记日前连续12个月(以一个月为1个纳税期限)或者连续4个季度(以一个季度为一个纳税期)累计销售额未超过500万元的一般纳税人,在2019年12月31日前,可转登记为小规模纳税人,其未抵扣的进项税额()。
研究开发包括基础研究、应用研究和()。
某企业“应付账款”科目月末贷方余额40000元,其中:“应付甲公司账款”明细科目贷方余额25000元,“应付乙公司账款”明细科目贷方余额25000元,“应付丙公司账款”明细科目借方余额10000元;“预付账款”科目月末贷方余额20000元,其中:“预付A工
Whatisthewomanpreparing?
最新回复
(
0
)