首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明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
46
问题
阅读下列说明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.启动网络支持Linux系统运行级别3工作在______状态。A.单用户字符模式B.多用户字符模式
某交换机的配置命令如下,根据命令后面的注释,填写(1)~(3)处的空缺内容,完成配置命令。Switch(config)#(1)//将交换机命名为Sw1Swl(config)#interfacevlan1Swl(config
某交换机的配置命令如下,根据命令后面的注释,填写(1)~(3)处的空缺内容,完成配置命令。Switch(config)#(1)//将交换机命名为Sw1Swl(config)#interfacevlan1Swl(config
阅读以下说明,回答问题1至问题6。【说明】某公司在WindowsServer2003中安装IIS6.0来配置Web服务器,域名为www.abc.com。
在“管理工具”中运行“管理IP筛选器列表”,创建一个名为“SNMP消息”的筛选器。在如图12-3所示的“IP筛选器向导”中指定IP通信的源地址,下拉列表框中应选择(1);在如图12-4中指定IP通信的目标地址,下拉列表框中应选择(2)。在图
在校园网设计过程中,划分了很多VLAN,采用了VTP来简化管理。1.VTP信息只能在(1)端口上传播。2.运行VTP的交换机可以工作在三种模式:(2)、(3)、(4)。3.共享相同VLAN数据库的交换机构成一个(5)。该校园网采
该单位的公网IP地址范围是(1)到(2):其中该单位能够使用的有效公网地址有(3)个。为保证路由器的安全,网络管理员做了如下设置,请阅读下列三段路由配置信息,并在(4)~(6)处填写该段语句的作用。1.Router(Config)#noip
在控制面板的“添加/删除程序”对话框中选择(1),然后进入“应用程序服务器”选项,在(2)组件复选框中选择“文件传输协议(FTP)服务”,就可以在Windows2003中安装FTP服务。(1)A.更改或删除程序B.添加新程序C.添加/删除
在控制面板的“添加/删除程序”对话框中选择(1),然后进入“应用程序服务器”选项,在(2)组件复选框中选择“文件传输协议(FTP)服务”,就可以在Windows2003中安装FTP服务。(1)A.更改或删除程序B.添加新程序C.添加/删除
随机试题
前角型瘫痪表现不正确的是
简要病史:男性,21岁,多尿,烦渴2个月。要求:你作为住院医师,按照标准住院病例要求,围绕以上主诉,请叙述应如何询问该患者现病史及相关的内容。
急进性肾小球肾炎慢性期治疗措施最主要的是
填方土料应符合设计要求,一般不能选用的有()。
产业市场的采购行为一般属于理性购买,冲动性购买行为较少。()
下列关于税基大小和征税对象数量之间关系的说法,错误的是( )。
属于二级资质物业管理企业条件的是()。
在现实生活中,做人的学问往往比做事的学问更具有实用价值、更重要也更难掌握。做事仅靠技术就能________,做人则是一门弹性极强的艺术,讲求的是无法量化和________的分寸感。做事学一次即有毕业的可能,做人要活到老学到老,要一辈子下功夫。依次填入画横线
材料1“无论哪一个社会形态,在它所容纳的全部生产力发挥出来以前,是决不会灭亡的;而新的更高的生产关系,在它的物质存在条件在旧社会的胎胞里成熟以前,是决不会出现的。所以人类始终只提出自己能够解决的任务,因此只要仔细考察就可以发现,任务本身,只有在解
Home.FewwordsintheEnglishlanguagehavesuchaspecialmeaning.Homeisaplacewhereyoucanrelax,kickbackandjustbe
最新回复
(
0
)