首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务, 但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务, 但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
admin
2006-03-15
58
问题
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务,
但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任务。
程序中,N个任务从0开始依次编号,N个工人也从0开始依次编号,主要的变量说明如下:
c
[j]:将任务i分配给工人j的费用;
task
:值为0表示任务i未分配,值为j表示任务i分配给工人j;
worker[k]:值为0表示工人k未分配任务,值为1表示工人k已分配任务;
mincost:最小总费用。
【C程序】
#include<stdio.h>
#define N 8 /*N表示任务数和工人数*/
int c[N][N];
unsigned int mincost=65535; /*设置min的初始值,大于可能的总费用*/
int task[N],temp[N],workerIN];
void Plan(int k,unsigned Int cost)
{ int i;
if ((1)&&cost<mincost){
mincost=cost;
for (i=0;i<N;i++) temp
:task
;
}
else{
for(i=0;i<N;i++) /*分配任务k*/
if (worker
=0&&(2)){
worker
=1; task[k]=(3);
Plan((4),cost+c[k]
);
(5); task[k]=0;
}/*if*/
}
}/*Plan*/
void main()
{int i,j;
for (i=0;i<N;i++) { /*设置每个任务由不同工人承担时的费用及全局数组的初值*/
worker
=0;task
=0; temp
=0;
for(j=0;j<N;j++)
scanf ("%d",&c
[j]);
}
Plan (0,0); /*从任务0开始分配*/
printf("\n最小费用=%d\n",mincost);
for(i二0;i<N;i++)
pnntf("Task%d iB assigned toWorker%d\n",i,temp
);
}/*main*/
选项
答案
(1)k>=N,或k==N,或其等价形式 (2)cost+e[k][i]<mincost,或其等价形式 (3)i (4)k+1 (5)worker[i]=0,或其等价形式
解析
首先为函数Plan()代码加上行号,以便说明。
1:void Plan(ihtk,unsigned int cost)
2:{int i;
3: if( (1) &&cost<mincost){
4: mincost=cost;
5: for(i=0;i<N;i++) temp
=task
;
6: }
7: else{
8: for(i=0;i<N;i++) /*分配任务k*/
9: if (worker
=0&& (2) ){
10: worker
=1; task[k]= (3) ;
11: Plan( (4) ,cost+c[k]
);
12: (5) ; task[k]=0;
13: }/*if*/
14: }/*else*/
15:}/*Plan*/
由注释可知,在Plan(k,cost)中,以k表示任务编号、cost表示费用。根据题目中的说明,程序用回溯法计算总费用最小的一种工作分配方案,因此在得到每一个分配方案时需要和先前已经得到的分配方案中的最小费用进行比较。由于需要将N个任务分配给N个工人,以任务为序时,最后一个任务(第N-1个任务)分配之后便得到一种方案,因此第3行代码的空(1)处填入“k>=N或k==N”。
显然,在分配任务k时,需要考查所有的工人(第8行代码),此时若工人i尚未接收任务(worker
==0),并且将任务k分配给工人i不会超出前面某个方案的费用,则可将任务k分配给他(task[k]=i,然后开始分配第k+1个任务。回溯时则需要将分配工人i的任务撤销,以便考查其他的分配方案。
转载请注明原文地址:https://kaotiyun.com/show/zfDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
某数据库中有供应商关系S和零件关系P,其中,供应商关系模式S(Sno,Sname,SZip,City)中的属性分别表示;供应商代码、供应商名、邮编、供应商所在城市;零件关系模式P(Pno,Pname,Color,Weight,City)中的属性分别表示:
v模型指出,(47)对程序设计进行验证,(48)对系统设计进行验证,(49)应当追溯到用户需求说明。
在软件生命周期的不同阶段,需要实施不同类型的测试工作,单元测试是对程序设计进行验证,其中(39)不是单元测试的主要内容。在进行单元测试过程中,通常测试工程师都需要借助(40)来代替所测模块调用的子模块;在单元测试的基础上,需要将所有模块按照概要设计和详细设
请根据下面叙述的场景选用适当的设计模式。若某面向对象系统中的某些类有且只有一个实例,那么采用(30)设计模式能够有效达到该目的:该系统中的某子模块需要为其他模块捉供访问不同数据库系统(如 Oracle、SQL Server和DB2 UDB等)的功能,这些数
某供应商数据库中的供应关系为SPJ(供应商号,零件号,工担号,数量),如下命令查询某工程至少用了3家供应商(包含3家)供应的零件的平均数量,并按工程号的降序排列。SELECT工程号,(14)FROMSPJGROUPBY工程号(15)
某系统的进程状态转换如下图所示。图中1、2、3和4分别表示引起状态转换时的不同原因。原因4是由于(9);一个进程状态转换会引起另一个进程状态转换的是(10)。
以下(53)属于在GB/T18905《评价者用的过程》中定义软件评价过程的特性。①可重复性②可再现性③公正性④客观性⑤合理性
以下各项中,(51)属于需求说明书的评测内容。①系统定义的目标是否与用户的要求一致②设计的约束条件或限制条件是否符合实际③是否考虑过软件需求的其他方案④软件的行为与它必须处理的信息、必须完成的功能是否一致
随机试题
A.疝内容物易回纳入腹腔B.疝内容物不能完全回纳入腹腔C.疝内容物有动脉性血循环障碍D.疝内容物被疝环卡住不能还纳,但无动脉性循环障碍E.疝内容为部分肠壁嵌顿性疝
业务指导文件既是订货的原始凭证,也是供求双方进发业务的合同,应分类、分版保管。()
哪一项检查是骨质疏松最敏感的检查方法
小儿患病后易趋康复的主要原因是
下列各项中,不体现实质重于形式要求的是()。
下列各项中,应当按照“销售货物”征收增值税的有()。
6枚一角硬币叠在一起与5枚五角硬币一样高,6枚五角硬币叠在一起与5枚一元硬币一样高。如果分别用一角、五角、一元硬币叠成三个一样高的圆柱,这些硬币的币值为87.2元,那么三种硬币总共多少枚?
A、 B、 C、 D、 C
根据我国宪法和法律,下列关于公民财产权的表述,正确的是()。
Lastyear’seconomyintheUnitedStatesshouldhavewontheOscarforbestpicture.Growthingrossdomesticproductwas4.1pe
最新回复
(
0
)