首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务, 但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务, 但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
admin
2006-03-15
45
问题
阅读以下说明和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是该模块的类图,图中属性和操作前的“+”
对于业务流清晰的系统可以利用(57)贯穿整个测试用例设计过程,在用例中综合使用各种测试方法,对于参数配置类的软件,要用(58)选择较少的组合方式达到最佳效果,如果程序的功能说明中含有输入条件的组合情况,则一开始就可以选用(59)和判定表驱动法。
在软件生命周期的不同阶段,需要实施不同类型的测试工作,单元测试是对程序设计进行验证,其中(39)不是单元测试的主要内容。在进行单元测试过程中,通常测试工程师都需要借助(40)来代替所测模块调用的子模块;在单元测试的基础上,需要将所有模块按照概要设计和详细设
多条件覆盖是一种逻辑覆盖,它的含义是设计足够的测试用例,使得每个判定中条件的各种可能组合都至少出现一次,满足多条件覆盖级别的测试用例也是满足(44)级别的;针对布尔表达式A&&(B‖C)执行逻辑覆盖测试,测试用例至少需要(45)种组合才能满足多条件覆盖的要
(61)方法根据输出对输入的依赖关系设计测试用例。
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
随机试题
在对市场营销成本进行分析之后,还应该考察以下几个反映企业盈利能力的指标:
某公路工程路线长2.192km,其中软土地基路段约400m,填土高度平均4.5m,位于冲积平原,地层厚度均匀,层位稳定,地层主要由第四系新近沉积的淤质土和第四系下更新统的灰、杂色粘土和砂层构成。其层次由上至下分别为粘土(硬壳层)、淤泥质粉质粘土、粉质粘土、
当前在建设工程管理领域中信息化的重要标志是()。
因故不能按时开工的,应当向发证机关申请延期,延期以()为限。
根据物权法律制度的规定,下列各项中,不属于物权的原始取得的是()。
以下情形中,可以申请个人住房贷款的是()。
实行内部成本核算的事业单位,购入无形资产发生的支出,应在受益期内分期平均摊销。()
简述我国实行既统一又分层的立法体制的原因。
历代文人墨客对西湖吟诗赋词。因此,西湖为后人留下了底蕴丰厚的文学资源。以下哪个诗句是描写西湖的?()
ThemainpurposeofEnglishessaywritingistointroduceyoutotheconventionsofacademicwritingandcriticalthinking.
最新回复
(
0
)