首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
37
问题
阅读下列说明和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();}
考虑6个作业的实例,各个作业在两台处理机上的处理时间如下表所示。该实例的最优解为
(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]Ix]+b[k],F[k一1][x—a[k]]};其中F[k一1]Ix]+b[k]表示第k个作业由机器B来处理(完成k一1个作业时机器A花费的时间仍是x),F[k一1][x—a[k]]表示第k个作业由机器A处理(完成k一1个作业时机器A花费的时间是x—aEk]。
那么单个点对较大值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][0]=3,则Max(0,3)=3,机器A花费0时间,机器B花费3时间,而此时两个机器所需时间为3;
x=1时,F[0]E1]=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[1])。
当x<0时,记F[1][x]=∞;这个记法编程使用,因为数组下标不能小于0。在这里的实际含义是:X是代表完成前两个作业机器A的时间,a[1]是机器A完成第2个作业的时间,若x<a[1],则势必第2个作业由机器B来处理,即在Min()中取前者。
X=0,则F[1][0]=Min{F[0][0]+b[2],F[0][0-a[1]])
=Min{3+8,∞}=11,进而Max(0,11)=11;
X=1,则F[1][1]=Min{F[0][1]+b[2],F[[0][1-a[1]]}
=Min{3+8,∞)=11,进而Max(11)=11;
X=2,则F[1][2]=Min{F[0][2]+b[2],F[[0][Z-a[1]]}
=Min{0+8,∞)=8,进而Max(2,8)=8;
X=3,则F[1][3]=Min{F[0][3]+b[2],F[0][3一a[1]]}
=Min{0+8,∞)=8,进而Max(3,8)=8;
X=4,则F[1][4]=Min{F[0]E4]+b[2],F[0]E4-a[1]]}
=Min(0+8,∞)=8,进而Max(4,8)=8;
X=5,则F[1][5]=Min{F[0]E5]+b[2],F[0][5-a[1]]}
=Min(0+8,3)=3,进而Max(5,3)=5;
X=6,则F[1][6]=Min(F[0][6]+b[2],F[0][6-a[1]])
=Min{0+8,3)=3,进而Max(6,3)=6;
x=7,则F[1][7]=Min{F[0][7]+b[2],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/1iDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
()主要对与设计相关的软件体系结构的构造进行测试。
以下关于建立良好的程序设计风格的叙述中,正确的是()。
在软件评审中,设计质量是指设计的规格说明书符合用户的要求。设计质量的评审内容不包括______。
由于操作系统升级而对软件进行修改的行为属于________维护。
在C程序中,设有“inta=3,b=2,c=1;”,则表达式a>b>c的值是_________。
[Java源程序:一个简单的Web服务器]/************************************************************//*WebServer.java*//******
SSL协议使用(1)密钥体制进行密钥协商。在IIS5.0中,Web服务器管理员必须首先安装Web站点数字证书,然后Web服务器才能支持SSL会话,数字证书的格式遵循ITU-T(2)标准。通常情况下,数字证书需要由(3)颁发。如果Web服务器管理员准备预
阅读以下说明,回答问题1~6。[说明]某公司已有一个100用户的有线局域网。由于业务的发展,现有的网络不能满足需求,需要增加40个用户的网络连接,并在公司客户接待室连接网络以满足合作伙伴实时咨询的需求。现结合公司的实际情况组建无线局域网,具体拓扑
认真阅读下列说明信息,回答问题1至问题5。[说明]在一个基于TCP/IP协议的网络中,每台主机都有一个IP地址,根据获得IP地址的方式不同,可以分为静态IP和动态IP。例如:用宽带入网,会有一个固定的IP地址,每次连入Internet,你的IP地
从下列选项中选取合适的答案分别填入图4-1中的(1)~(4)处。A.DES算法B.MD5算法C.会话密钥D.数字证书E.甲的公钥F.甲的私钥G.乙的公钥H.乙的私钥当乙收到了地
随机试题
某伤害案件,在审查起诉过程中,被害人向人民检察院提出了附带民事诉讼的要求,要求赔偿医药费和误工损失费3000元,但人民检察院经鉴定确定伤害人的伤情为轻微伤,对刑事案件作出不起诉的处理决定,对被害的赔偿要求应当如何处理?
学校要依法治校,教师要依法执教,切实保障学生的合法权利,因此对学生的奖惩都要()。
A.K-B.Na+C.Ca2+D.Cl-E.Mg+可产生抑制性突触后电位的离子基础是
某房地产估价师运用市场法和假设开发法对一宗4270m2的商业用地于2007年10月21日的土地使用权价格进行评估,该宗地的剩余使用期限为39年,两种估价方法测算出的结果分别为2000元/m2和2300元/m2。假设2006年10月和2007年10月该区域的
某电建公司通过招投标承揽到一座2×1OOMW火力发电厂的主体工程安装项目。该安装工程在整个发电厂建设项目中属于其中的一项单位工程,该电建公司将其中的非标制作工程、通风工程等分部工程分包给某机械制造厂和一些专业承包单位。各专业工程陆续开展工程质量检查、验收与
下列表达式中,弗里德曼的货币需求函数是( )。
物业管理投标的主要风险来自于招标人和招标物业、投标人、竞争对手,下列选项中,属于来自竞争对手的风险是()。
目前,中国实行的是以市场供求为基础的,单一的、有管理的浮动汇率制度,这既符合中国实际情况,又体现了对国际社会的高度负责。我国坚决反对美国少数政客出于国内政治需要,利用汇率问题打压其他国家,强迫别国货币升值。这是因为从根本上说()。
IntheUnitedStates,thefirstday-nurserywasopenedin1854.@Nurserieswereestablishedinvariousareasduringthe(1)_____
Inthebestof(36)______,thenextadministrationwillbebesetby(37)______.Inalmosteveryareaoftheworld,wehavebeen
最新回复
(
0
)