首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务, 但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务, 但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
admin
2006-03-15
41
问题
阅读以下说明和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个档次,由乘机次数和点数共同决定,如表2-1所示。其中点数跟票面价格和购票渠道有关,规则如表2-2所示。航空公
阅读下列C程序,回答问题,将解答填入答题纸的对应栏内。【C程序】intisbinary(constvoid*buf,constsizetbuf—fen){sizetsuspiciousbytes=0;sizettotal—by
操作数所处的位置,可以决定指令的寻址方式。操作数包含在指令中,寻址方式为(4);操作数在寄存器中,寻址方式为(5);操作数的地址在寄存器中,寻址方式为(6)。
多条件覆盖是一种逻辑覆盖,它的含义是设计足够的测试用例,使得每个判定中条件的各种可能组合都至少出现一次,满足多条件覆盖级别的测试用例也是满足(44)级别的;针对布尔表达式A&&(B‖C)执行逻辑覆盖测试,测试用例至少需要(45)种组合才能满足多条件覆盖的要
黑盒测试是通过软件的外部表现来发现软件缺陷和错误的测试方法,具体地说,黑盒测试用例设计技术包括(42)等。现有一个处理单价为1元的盒装饮料的自动售货机软件,若投入1元币,按下“可乐”、“雪碧”或“红茶”按钮,相应的饮料就送出来,若投入的是2元币,在送出饮料
(61)方法根据输出对输入的依赖关系设计测试用例。
请根据下面叙述的场景选用适当的设计模式。若某面向对象系统中的某些类有且只有一个实例,那么采用(30)设计模式能够有效达到该目的:该系统中的某子模块需要为其他模块捉供访问不同数据库系统(如 Oracle、SQL Server和DB2 UDB等)的功能,这些数
某供应商数据库中的供应关系为SPJ(供应商号,零件号,工担号,数量),如下命令查询某工程至少用了3家供应商(包含3家)供应的零件的平均数量,并按工程号的降序排列。SELECT工程号,(14)FROMSPJGROUPBY工程号(15)
GB/T16260将软件的内部(外部)质量属性划分为六大质量特性,分别是(65)。
风险分析在软件项目开发中具有重要作用,包括风险识别、风险预测、风险评估和风险控制等。“建立风险条目检查表”是(18)时的活动,“描述风险的结果”是(19)时的活动。
随机试题
()是监督基金管理人的投资运作行为是否符合法律法规及基金合同的规定。
下列不属于习近平主席在亚洲文明对话大会开幕式上的主旨演讲提出的是:
沙门菌的Vi抗原是指
急性脑血栓形成患者,用低分子右旋糖酐的目的是
胃溃疡最主要的症状是
()是组织最活跃的因素,也是最有不确定性的因素。
目前,一大中城市制定丫残疾人乘坐公共交通免费的政策,这满足了残疾人()的基本需求。
学校文化的功能包括()。
孔子在中国历史上留下了光辉的文化轨迹,以下关于孔子的说法正确的是()。
Overall,beliefinclimatechangehasdeclinedintheAmericanpublicfromroughly75percentto55percentbetween2008and201
最新回复
(
0
)