首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2012年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在
(2012年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在
admin
2018-07-27
31
问题
(2012年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为a
i
和b
i
。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业,在B上处理时间长。一台处理机在某个时刻只能处理一个作业,而且作业处理是不可中断的,每个作业只能被处理一次。现要找出一个最优调度方案,使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
算法步骤:
(1)确定候选解上界为R短的单台处理机处理所有作业的完成时间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)(||表示逻辑或操作)。
(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<stdio.h>
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<n;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
}
}
}
printf(’’\n%d\n’’,max);
}
void main(){read();schedule();write();}
考虑6个作业的实例,各个作业在两台处理机上的处理时间如表9.5所示。该实例的最优解为_____(7),最优解的值(即最短处理时间)为_____(8)。最优解用(x
1
,x
2
,x
3
,x
4
,x
5
,x
6
)表示,其中若第i个作业在A上处理,则x
i
=1,否则
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][0]=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[1])。
x<0时,记F[1][x]=∞;这个记法编程使用,因为数组下标不能小于0。在这里的实际含义是:x是代表完成前两个作业机器A的时间,a[1]是机器A完成第二个作业的时间,若x<a[1],则势必第二个作业由机器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(1,11)=11。
x=2,则F[1][2]=min{F[0][2]+b[2],F[0][2-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][4]+b[2],F[0][4-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[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/c7DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明然后完成问题1、问题2、问题3、问题4,把答案填入相应的对应栏内。[说明]如图10-1是Cisco1900交换机划分为两个vain拓扑图,把E0/10划分为vlan2,把E0/20划分为vlan3。[*]
请说出图9-1的拓扑结构名称与特点。根据IP地址与子网掩码,请判断它们是否属于同一个网段?如果不是,请说出他们分别属于哪个网段。
阅读以下说明,回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。[说明]以太网宽带接入方式是目前许多居民小区所普遍采用的,其方式为所有用户都通过一条主干线接入Internet,每个用户均配备个人的私有IP地址,用户只需将小区
从图7-1中可以看出采用什么拓扑结构与设计方法?为了进一步简化系统,有人建议把“电脑模块”与“电话模块”合成一个模块,其传输介质共用,这可以实现吗?
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]现在,家居装修布线是一个大且细致的工程项目,除了要布设普通电源线、有线电视电缆和电话线、音响线、视频线等,越来越多的电脑爱好者家中的网络布线则是少不了的。如果不是
将图2-2中(1)和(2)空缺名称填写在对应的解答栏内。使ADSL的传输速率更高有哪两个主要因素?
认真阅读下列有关Linux操作系统的Samba配置技术的说明,根据要求回答问题1至问题6。【说明】SMB(ServerMessageBlock,服务消息块)协议主要用于实现Windows和Linux操作系统中计算机之间共享打印机、共享串行接
在图8-12所示的拓扑结构中的代理服务器上依次单击“开始→程序→管理工具→路由与远程访问,并在系统弹出的界面中打开“IP路由选择”目录树,然后用鼠标右键单击“NAT/基本防火墙”,选择[新增接口]命令。接着若选择接口1的“本地连接”,最后进行如图8-13所
随机试题
简要回答《2010年通则》中的CPT术语和CFR术语的区别。
10岁儿童头颈部(包括头部、面部、颈部)烧伤,其烧伤面积占体表总面积的()
HBsAg(一)抗-HBs(+)HBe-Ag(一)抗Hbe(一),表明
下列各选项中,不作为土地权属争议案件受理的案件不包括()。
企业发生的交易中,如果涉及补价,判断该项交换属于非货币性资产交换的标准有()。
独立性差、易受暗示,经常不加批判地接受别人的意见,照别人的意见办事,在紧急、困难的情况下表现得惊慌失措,这种性格类型是()。
依次填入横线部分最恰当的一项是()。梳理这一事件的来龙去脉并不复杂,无论承包商还是开发商,都存在不规范之处,甚至涉嫌违法违规。他们三番五次地侵犯农民工的合法权益,____________,____________,____________,理应受到约束和
有8人要在某学术报告会上作报告,其中张和李希望被安排在前三个作报告,王希望最后一个作报告,赵不希望在前三个作报告,其余4人没有要求。如果安排作报告顺序时要满足所有人的要求,则共有多少种可能的报告序列?()
Writealetterofabout100wordstorecommendyourfriend,ZhangYing,whoisapplyingforajobtoteachChineseinAmerica.
A、北方B、南方C、东部D、西部A语段说“北方地区受冷空气影响,局部地区降温达8℃”,所以选择A。
最新回复
(
0
)