首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C程序,将应填入(n)处的字句写在对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务,但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配 1个不同的任务。
阅读以下说明和C程序,将应填入(n)处的字句写在对应栏内。 【说明】 假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务,但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配 1个不同的任务。
admin
2009-05-15
40
问题
阅读以下说明和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)业务。
DQDB同时支持(26)两种服务。DQDB子网的双总线结构由(27)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(28)访问控制方式,其中能够提供非等时服务是(29),它用于(30)业务。
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
以下关于程序运行时内存分配区域的描述中,说法错误的是(12)。
Linux中一种常用的引导工具是(51);在Linux操作系统下安装网卡,如果操作系统没有内置的驱动程序,那么用户必须(52),才能完成驱动程序的安装;为一块设备名为eth0的网卡分配IP地址和子网掩码的命令是:(53);如果不打算使用DNS或者NIS进行
随机试题
作为一个单纯的图书设计者,设计师需要尊重书籍本身而适度地“__________”自己,即不能“过度设计”而使形式僭越了书籍内容。但是,作为一个创意表达者,设计师一旦参与了图书的创作,就使书籍成为表达自己独特创意的__________,此时设计师已不仅仅干预
A.病理性激情B.矛盾情感C.强制性哭笑D.焦虑E.情感倒错癫痫所致精神障碍常见
麦冬所含的甾体皂苷元主要为()。
下列哪种情形构成对生命权的侵犯?()
珠海某公司委托深圳某公司进口一批设备,拟从广州口岸入境,最终运至东莞某加工厂。该批设备申请检验的地点是()。
本票必须记载的事项包括()。
老谋深算属于()。
光棍节
在数据库系统的内部结构体系中,索引属于()。
计算机的应用原则上分为哪两大类?
最新回复
(
0
)