首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明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上处理时间长。一
admin
2014-11-13
49
问题
阅读下列说明C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为a
i
和b
i
。由于各个作业的特点和机器性能的关系,对某些作业,在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;k
P[x][y][k]=0;
}
}
for(k=1;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]=(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代码,算法的时间复杂度为(6)(用O符号表示)。
选项
答案
(6)O(m
2
n)
解析
从程序的循环层数即可看出算法的时间复杂度。程序的最高循环层数为3层。最外层循环变量的变化范围是1一n一1,次外层循环变量的变化范围是0~m,内层循环变量的变化范围是0~m,所以时间复杂度为O(m
2
n)。
转载请注明原文地址:https://kaotiyun.com/show/bpDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持根据说明中inittab文件的内容,系统引导成功后,工作在______状态。A.单用户字符模式
阅读以下说明,回答问题1至问题6。【说明】某公司在WindowsServer2003中安装IIS6.0来配置Web服务器,域名为www.abc.com。
销售部的网络号是(1),广播地址是(2):技术部的网络号是(3),广播地址是(4);每个子网可用的IP地址有(5)个。Linux网关计算机有两个网络接口(eth0和eth1),每个接口与对应的子网相连接。该计算机/etc/sysconfig,/
阅读以下关于Linux网关安装和配置过程的说明,回答问题1至问题5。【说明】当局域网中存在大量计算机时,根据业务的不同,可以将网络分成几个相对独立的子网。图12-2是某公司子网划分的示意图,整个网络被均分为销售部和技术部两个子网,子网之间通过一台
在校园网设计过程中,划分了很多VLAN,采用了VTP来简化管理。1.VTP信息只能在(1)端口上传播。2.运行VTP的交换机可以工作在三种模式:(2)、(3)、(4)。3.共享相同VLAN数据库的交换机构成一个(5)。该校园网采
请阅读下列SwitchA的配置信息,并在(1)~(5)处解释该语句的作用。Switch>enable(进入特权模式)Switch#configterminal(进入配置模式)Switch(config)#hostnameSwi
请阅读下列SwitchA的配置信息,并在(1)~(5)处解释该语句的作用。Switch>enable(进入特权模式)Switch#configterminal(进入配置模式)Switch(config)#hostnameSwi
阅读以下说明,回答问题1至问题4。【说明】图5-1是VLAN配置的结构示意图。
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址图3-3是DHCP服务器安装中的添加排除窗口。 参照图
从网络拓扑图中可以看出该校园网采用了分层设计结构,回答以下问题:1.交换机按照所处的层次和完成的功能分为三种类型:核心交换机、汇聚交换机和接入交换机。下表是学校采购的三种交换机,请根据交换机的技术指标确定交换机的类型。在答题纸对应的解答栏内
随机试题
1941年9月,中国民主政团同盟创办了盟报
A、expressB、extraC、expertD、exportAe在A项中读[i],而在B、C、D三项中读[e]。
下列哪项不是引起空腹高血糖的原因
尿潴留可分为________和________,病因可分为________,其中常见________。
下列何项不是桑菊饮与银翘散组成中均有的药物
常用的统计调查方式有()。
下列关于不确定性的表述中,正确的是( )。
下列关于上市公司股份锁定期的说法正确的有()。Ⅰ.控股股东持有的首次公开发行股票前已发行股份,应锁定36个月Ⅱ.国外战略投资者取得的上市公司A股股份,应锁定36个月Ⅲ.境内战略投资者认购上市公司非公开发行的股份,应锁定
政策评估是对效果进行研究,是决定政策走向的依据,是合理配置政策资源的基础,是迈向决策科学化的途径。以下()不属于政策评估的基本内容。
把下面的六个图形分为两类,使每一类图形都有各自的共同特征或规律,分类正确的一项是()。
最新回复
(
0
)