首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明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
66
问题
阅读下列说明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();)
考虑6个作业的实例,各个作业在两台处理机上的处理时间如表15一1所示。该实例的最优解为(7),最优解的值(即最短处理时间)为(8)。最优解用(x
1
,x
2
,x
3
,x
4
,x
5
,x
6
)表示,其中若第i个作业在A上处理,则x
i
=1,否则x
i
=2。如(1,1,1,1,2,2)表示作业1,2,3和4在A上处理,作业5和6在B上处理。
选项
答案
(7)(1,1,2,2,1,1)(8)15
解析
为了方便考生更好地理解本算法的思想,现做如下分析:当完成k个作业,设机器A花费了x时间,机器B所花费时间的最小值肯定是x的一个函数,设F[k][x]表示机器B所花费时间的最小值,则F[k][x]=Min{F[k—1][x]+b[k],F[k.1][x—a[k]]}。其中F[k—1][x]+b[k]表示第k个作业由机器B来处理(完成k-1个作业时机器A花费的时间仍是x),F[k—1][x.a[k]]表示第k个作业由机器A处理(完成k—1个作业时机器A花费的时间是x-a[k])。那么单个点对较大值max(x,F[k][x]),表示此时(即机器A花费X时间的情况下)所需要的总时间。而机器A花费的时间x是变化的,即x=0,1,2…x(max),由此构成了点对较大值序列。要求整体时间最短,取这些点对较大值序列中最小的即是。现分析前两个作业的情况:对于第一个作业:下标以0开始。首先,机器A所花费时间的所有可能值范围:0<=x<=a[0]。设x<0时,设F[0][x]=∞,则max(x,∞)=∞。记法意义见下。x=0时,F[0][01=3,则max(0,3)=3,机器A花费0时间,机器B花费3时间,而此时两个机器所需时间为3;x=1时,F[0][1]=3,max(1,3)=3;x=2时,F[0][2]=0,则max(2,0)=2;那么上面的点对序列中,可以看出当x=2时,完成第一个作业两台机器花费最少的时间为2,此时机器A花费2时间,机器B花费0时间。再来看第二个作业。首先,x的取值范围是:0<=X<=(a[0]+a[11)。当x<0时,记F[1][x]=∞。这个记法编程使用,因为数组下标不能小于0。在这里的实际含义是:x是代表完成前两个作业机器A的时间,a[1l是机器A完成第2个作业的时间,若x
x=0,NF[1][0]=min{F[0][0]+b[21,F[0][0—a11]1)=min{3+8,∞)=11,进而max(0,11)=11;
x=l,则F[1][1]=min{F[0][1]+b[2],F[0][1—a[1]]}=min{3+8,∞}=11,进而max(11)=11;
x=2,则F[I][21=min{F[0][2]+b[2],F[0][2一a[11]}=min{0+8,∞}=8,进而max(2,8)=8;
x=3,则F[1][3]=min{F[0][3]+b[2],F[0][3一a11]])=min{0+8,∞)=8,进而max(3,8)=8;
x=4,则F[1][4]=min{F[0114]+b[2],F[0114一a[1]])=min{0+8,∞}=8,进而max(4,8)=8;
x=5,则F[1][5]=min{F[0][5]+b[2],F[0][5一a[1]]}=min{0+8,3}=3,进而max(5,3)=5;
x=6,则F[11161=min{F[0l[6]+b[21,F[0][6一a[1]]}=min{0+8,3l=3,进而max(6,3)=6:
x=7,则F[1l[71=min{F[0l[7]+b[21,F[0][7一a[1]}=min{0+8,0)=0,进而max(7,0)=7;
那么上面的点对序列中,可以看出当x=5时,完成两个作业两台机器花费最少的时间为5,此时机器A花费5时间,机器B花费3时间。接下来依次类推即可,最终该实例的最优解为(1,1,2,2,1,1),最短处理时间为15。这里提供当各个作业完成时的最短处理时间,考生可自行推导:2,5,7,12,14,15。
转载请注明原文地址:https://kaotiyun.com/show/EpDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
某交换机的配置命令如下,根据命令后面的注释,填写(1)~(3)处的空缺内容,完成配置命令。Switch(config)#(1)//将交换机命名为Sw1Swl(config)#interfacevlan1Swl(config
在“管理工具”中运行“管理IP筛选器列表”,创建一个名为“SNMP消息”的筛选器。在如图12-3所示的“IP筛选器向导”中指定IP通信的源地址,下拉列表框中应选择(1);在如图12-4中指定IP通信的目标地址,下拉列表框中应选择(2)。在图
销售部的网络号是(1),广播地址是(2):技术部的网络号是(3),广播地址是(4);每个子网可用的IP地址有(5)个。设置技术部和销售部的主机网络参数后,如果两个子网间的主机不能通信,用(13)命令来测试数据包是否能够到达网关计算机。如果数据包可以达到
销售部的网络号是(1),广播地址是(2):技术部的网络号是(3),广播地址是(4);每个子网可用的IP地址有(5)个。在网关计算机/etc/sysconfig/network-scripts/目录中有以下文件,运行某命令可以启动网络,该命令是(9),其
在校园网设计过程中,划分了很多VLAN,采用了VTP来简化管理。1.VTP信息只能在(1)端口上传播。2.运行VTP的交换机可以工作在三种模式:(2)、(3)、(4)。3.共享相同VLAN数据库的交换机构成一个(5)。该校园网在
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址在DHCP服务器安装完成后,DHCP控制台如图3-4所示。
请选择恰当的内容填写在(1)、(2)、(3)空白处。一般用Host表、网络信息服务系统(NIS)和域名服务(DNS)等多种技术来实现主机名和IP地址之间的转换。Host表是简单的文本文件,而DNS是应用最广泛的主机名和IP地址的转换机制,它使用(1
从网络拓扑图中可以看出该校园网采用了分层设计结构,回答以下问题:1.交换机按照所处的层次和完成的功能分为三种类型:核心交换机、汇聚交换机和接入交换机。下表是学校采购的三种交换机,请根据交换机的技术指标确定交换机的类型。在答题纸对应的解答栏内
从网络拓扑图中可以看出该校园网采用了分层设计结构,回答以下问题:1.交换机按照所处的层次和完成的功能分为三种类型:核心交换机、汇聚交换机和接入交换机。下表是学校采购的三种交换机,请根据交换机的技术指标确定交换机的类型。在答题纸对应的解答栏内
在控制面板的“添加/删除程序”对话框中选择(1),然后进入“应用程序服务器”选项,在(2)组件复选框中选择“文件传输协议(FTP)服务”,就可以在Windows2003中安装FTP服务。(1)A.更改或删除程序B.添加新程序C.添加/删除
随机试题
小蓟饮子组成中含有胶艾汤组成中含有
患儿,男童,8岁。右下第一恒磨牙深龋,去除大块腐质,近髓处留少许软化牙本质,上方用Ca(OH)2盖髓后充填。下次复诊进行二次去腐质的时间是
根据《建设工程质量管理条例》,建设工程竣工验收应当具备的条件包括()。
乙股份有限公司(以下简称“乙公司”)为华东地区的一家上市公司,属于增值税一般纳税人。乙公司2014年至2017年与固定资产有关的业务资料如下:(1)2014年12月1日,乙公司购入一条需要安装的生产线,取得的增值税专用发票上注明的生产线售价为1170万元
亲生父母双方都有高血压的人,得高血压的几率是亲生父母都没有高血压的人的5倍。所以,高血压可能是一种遗传病。下列哪项为真,最能支持上述结论?()
所谓声誉,实际上是企业利益相关者对企业过去在市场交易中的表现的评价。声誉良好的企业,意味着在与利益相关者交易的历史中,扮演着可以信赖的伙伴角色。个人或者组织选择自己的交易对象,__________。因此,那些有着良好信用记录的企业,将更多地获得利益相关方的
明太祖为巩固和扩大里老司法审判权而制定的法规是()。
在塞普西路斯的一个古城蒙科云,发掘到了城市的残骸,这一残骸呈现出被地震损坏的典型特征。考占学家猜想,该城的破坏是这个地区公元365年的一次地震所致。以下哪项,如果为真,及有力地支持了考古学家的猜想?
下面是一段关于劳动创造价值论的材料:第二次世界大战以后,一些发达资本主义国家生产自动化水平达到了空前规模。20世纪60年代工业机器人的出现,使得资本主义生产过程中,除了“蓝领”和“白领”以外又增添了“钢领”即机器人。据此,西方一些经济学
Itisplaincommonsense—themorehappinessyoufeel,thelessunhappinessyouexperience,butitisnottrue.Recentresearchr
最新回复
(
0
)