首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务, 但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务, 但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
admin
2006-03-15
39
问题
阅读以下说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】在某嵌入式智能服务机器人的软件设计中,为了更好地记录机器人的个体信息和机器人的工作信息,为智能服务机器人设计了信息数据库。数据库主要完成收集智能服务机器人反馈信息的作用,记录所有机器人的所有工
阅读下列说明,回答问题,将解答写在答题纸的对应栏内。某汽车维修公司的工时计算模块每天定时根据系统登记的维修信息统计维修工的工时工资。维修工分为学徒、普通维修工和高级维修工三种,三种维修工有不同的时薪标准。图4一1是该模块的类图,图中属性和操作前的“+”
阅读下列说明,回答问题,将解答写在答题纸的对应栏内。某汽车维修公司的工时计算模块每天定时根据系统登记的维修信息统计维修工的工时工资。维修工分为学徒、普通维修工和高级维修工三种,三种维修工有不同的时薪标准。图4一1是该模块的类图,图中属性和操作前的“+”
某数据库中有供应商关系S和零件关系P,其中,供应商关系模式S(Sno,Sname,SZip,City)中的属性分别表示;供应商代码、供应商名、邮编、供应商所在城市;零件关系模式P(Pno,Pname,Color,Weight,City)中的属性分别表示:
某数据库中有供应商关系S和零件关系P,其中,供应商关系模式S(Sno,Sname,SZip,City)中的属性分别表示;供应商代码、供应商名、邮编、供应商所在城市;零件关系模式P(Pno,Pname,Color,Weight,City)中的属性分别表示:
两个公司希望通过Internet进行安全通信,保证从信息源到目的地之间的数据传输以密文形式出现,而且公司不希望由于在传输节点使用特殊的安全单元而增加开支,最合适的加密方式是(10),使用的会话密钥算法应该是(11)。
对于业务流清晰的系统可以利用(57)贯穿整个测试用例设计过程,在用例中综合使用各种测试方法,对于参数配置类的软件,要用(58)选择较少的组合方式达到最佳效果,如果程序的功能说明中含有输入条件的组合情况,则一开始就可以选用(59)和判定表驱动法。
(61)方法根据输出对输入的依赖关系设计测试用例。
逻辑路径覆盖法是白盒测试用例的重要设计方法,其中语句覆盖法是较为常用的方法,针对下面的语句段,采用语句覆盖法完成测试用例设计,测试用例见下表,对表中的空缺项(True或者False),正确的选择是(60)。语句段:if(A&&(B‖C))
下列测试工具中,使用(68)执行自动化负载压力测试,使用(69)执行代码静态结构分析,使用(70)执行网络测试。
随机试题
诊断胸内结节病最常见、最重要的方法是下列哪项
女性,42岁。1944年胸部X线片据说有异常,但无症状。至1965年才感到双臂举过头顶时有困难,双睑午后下垂,并发觉视物成双。检查:双睑下垂,眨眼疲劳试验阳性,各眼外肌均无力。两臂上举过头只能坚持30秒,两下肢近端无力。面肌力弱,但无咽下困难与构音障碍。反
肝硬化上消化道出血诱发肝性脑病的主要机制是
同业拆借是银行为获得长期稳定的资金而相互之间进行的资金借贷。()
关于节俭。正确的说法是()。
李某放假回老家,在乘坐客运汽车的途中,被车窗外飞进的一块小石头击中左眼球,当场出血,被送往就近医院治疗,但因伤情严重导致失明。李某要求运输公司赔偿,但运输公司拒绝赔偿,理由是:李某的伤是外来的原因造成的,运输公司没有过错。李某和运输公司成立何种合同法律
下列关于抵押合同形式的表述,正确的是()。
社会主义初级阶段是我国社会主义不可逾越的一个历史阶段,这是因为()。
简述维果茨基的心理发展观。
在我国,人民民主的真谛是()
最新回复
(
0
)