首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务, 但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务, 但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
admin
2006-03-15
63
问题
阅读以下说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】在某嵌入式智能服务机器人的软件设计中,为了更好地记录机器人的个体信息和机器人的工作信息,为智能服务机器人设计了信息数据库。数据库主要完成收集智能服务机器人反馈信息的作用,记录所有机器人的所有工
在系统转换的过程中,旧系统和新系统并行工作一段时间,再由新系统代替旧系统的策略称为(20);在新系统全部正式运行前,一部分一部分地代替旧系统的策略称为(21)。
在GB/T 17544中,软件包质量要求包括三部分,即产品描述要求、(53)、程序和数据要求。
对于业务流清晰的系统可以利用(57)贯穿整个测试用例设计过程,在用例中综合使用各种测试方法,对于参数配置类的软件,要用(58)选择较少的组合方式达到最佳效果,如果程序的功能说明中含有输入条件的组合情况,则一开始就可以选用(59)和判定表驱动法。
下列测试工具中,使用(68)执行自动化负载压力测试,使用(69)执行代码静态结构分析,使用(70)执行网络测试。
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
某供应商数据库中的供应关系为SPJ(供应商号,零件号,工担号,数量),如下命令查询某工程至少用了3家供应商(包含3家)供应的零件的平均数量,并按工程号的降序排列。SELECT工程号,(14)FROMSPJGROUPBY工程号(15)
随机试题
年轻恒牙指
签订了书面估价委托合同之后,估价机构在未经委托人书面同意时,也可转让、变相转让受托的估价业务,并应明确至少一名合适的专职注册房地产估价师负责该估价项目。()
水利水电工程中,预可行性研究报告经主管部门审批后,即可编制()报告。
注册资金在20万元以上的个体工商户,按《个体工商户会计制度(试行)》规定应编制的会计报表包括()。
下列欧洲国家中,有“钟表王国”之称的是()。
“社区”一词,最早是由()社会学家滕尼斯于1887年在社会学名著《社区与社会》一书中提出的。
转动井口安装的辘轳手柄,可以轻松把水提取上来。这个辘轳应用的原理是:
下列说法正确的是:
下列选项中,哪些是按照文件的用途划分的文件分类?()
A、Shelikesyoungpeople,andwantstogetsomeexperienceonteaching.B、Shelikesworkingindependentlywithouttoomuchdirec
最新回复
(
0
)