首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C程序,将应填入(n)处的字句写在对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务,但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配 1个不同的任务。
阅读以下说明和C程序,将应填入(n)处的字句写在对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务,但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配 1个不同的任务。
admin
2009-05-15
43
问题
阅读以下说明和C程序,将应填入(n)处的字句写在对应栏内。
【说明】
假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务,但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配 1个不同的任务。
程序中,N个任务从0开始依次编号,N个工人也从。开始依次编号,主要的变量说明如下。
. 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; /*设置的初始值,大于可能的费用*/
int task[N], temp[N], worker[N];
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++)
printf("Task%d is assigned to Worker%d\n",i,temp
);
}/*main*/
选项
答案
(1) k==N或k>=N (2) cose+c[k][i]<mincost (3) i (4) k+1 (5) worker[i]=0
解析
本题考查回溯法的算法思想。
填充均集中在函数plan中,主函数main只是输入相关数据,调用plan函数,并输出结果。
函数的结构是一个if-else,在else块中调用了函数自身,因此该函数是一个递归函数,if块就是递归出口。在if块中,将cost赋值给mincost,而imncost是用来存储最小总费用的,接着将当前分配方案task保存到temp中,可见if块执行的条件是所有任务分配完成且当前总费用小于mincost。从main函数中调用plan(0,0)的注释:从任务0开始分配,可知,形参k表示当前分配的任务号,cost为当前分配的费用和。任务编号从0开始,故当编号为N时表示任务己分配完。故空(1)应填k==N。
else块中,从工人列表中找一个合适的工人分配任务k,并进行回溯,寻找最优解。函数的目的是寻找总费用最小的分配方案,因此当前分配费用和大于当前最好分配方案总费用的分配方案就不必考虑了。当然只有工人处于空闲状态才能给他分配任务。故空(2)应填cost+c[k]
<mincost。注意c[k]
表示将任务k分配给工人i的费用。task数组是用来记录任务分配情况的,在此将任务k分配给了工人i,故应将task[k]赋值为i。故空(3)应填i。空(4)处递归调用自身,自然是继续分配下一个任务,即任务k+1,故空(4)应填k+1。至此尚未回溯,空(5)正是用于回溯的,所谓回溯就是将上—个分配的任务换一种方案重新分配以遍历所有的分配方案,也可从紧接着的语句task[k]=0看出,将任务k置为未分配,既然任务k未分配,那么被分配工作的工人i也变为空闲。故空(5)应填worker
=0。
转载请注明原文地址:https://kaotiyun.com/show/o5xZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在OSI网络管理标准中定义了网络管理的5大功能。对历史数据进行分析、统计和整理,为未来的网络规划提供参考的功能属于(41);提供一系列实时数据采集、分析和可视化工具对流程、负载、丢包、温度、内存、延迟等网络设备和线路进行实时检测的功能属于(42);接收报警
DQDB同时支持(26)两种服务。DQDB子网的双总线结构由(27)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(28)访问控制方式,其中能够提供非等时服务是(29),它用于(30)业务。
FDDI与TokenRing都采用(21)传递协议,在FDDI的令牌帧中有(22),其主要作用是(23)。FDDI在(24)产生新令牌帧,允许在环上同时存在(25)。
FDDI与TokenRing都采用(21)传递协议,在FDDI的令牌帧中有(22),其主要作用是(23)。FDDI在(24)产生新令牌帧,允许在环上同时存在(25)。
IPv6是下一代IP协议,其基本报头中的(61)字段指明了一个特定的信源向某个特定信宿发送的分组序列,各个中间路由器要对该分组序列进行特殊处理以满足应用程序的特殊传输需求。
某公司为方便远程客户访问公司的某些数据资源,允许客户通过Internet访问公司的FTP服务器,其网络拓扑结构如图7—1所示。在客户机与FTP服务器之间采用(44)协议,可方便地实现在网络层对数据进行加密。
在UNIX操作系统中,以下Shell程序实现当用户键入的命令参数的个数为1时,执行cat$1命令;若用户键入的命令参数的个数为2时,执行cat>>$2<$1命令。case(36)in1)cat$1;;2)cat
基于IEEE802标准的CableMODEM参考体系结构中,(32)子层的主要功能是对射频(RF)载波进行调制/解调以获得数字比特流,并实现同步编码和差错校验。
ICMP报文封装在(24)协议数据单元中传送,在网络中起着差错和拥塞控制的作用。常用的ping程序中使用了回送请求/应答报文,以探测目标主机是否可以到达。
以下关于程序运行时内存分配区域的描述中,说法错误的是(12)。
随机试题
《国际货币基金协定》的主要内容包括()
假设按某种工艺生产的金属纤维的长度X(单位:mm)服从正态分布N(5.2,0.16),现在随机抽取15根纤维,测得它们的平均长度=5.3,如果总体方差没有变化,可否认为现在生产的纤维平均长度仍为5.2mm?(α=0.05)(附:u0.025=1.96)
护理学的4个基本概念是
女性淋病主要的感染部位是
A.组织接种单位销毁B.立即停止销售C.对该疫苗依法查封、扣押D.采取应急处置措施依照《疫苗流通和预防接种管理条例》的规定接到质量可疑疫苗报告的卫生主管部门应()
该租赁合同的性质属于()。若本案中双方未约定租赁期限,甲乙双方又无法就租赁期限协议补充,下列关于合同解除的说法正确的是()。
知图4—31所示斜面的倾角为θ,若要保持物块A静止,则物块与斜面之间的摩擦因数f所应满足的条件为()。
常见的金融风险类型包括()。
已知函数.f(x)=12/x+3x(x>0),则f(x)的最小值为________.
Obesityisanepidemictosomeandanopportunitytoothers.Morethantwo-thirdsofAmericansareoverweight.Findawaytobat
最新回复
(
0
)