设有m台完全相同的机器运行n个独立的任务，运行任务i所需的时间为ti，要求确定一个调度方案，使得完成所有任务所需要的时间最短。
假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略，按顺序先把每个任务分配到一台机器上，然后将剩余的任务依次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
1.常量和变量说明
m：机器数
n：任务数
t[]：输入数组，长度为n，下标从0开始，其中每个元素表示任务的运行时间，下标从0开始。
s[][]：二维数组，长度为m*n，下标从0开始，其中元素s[i][j]表示机器i运行的任务j的编号。
d[]：数组，长度为m其中元素d[i]表示机器i的运行时间，下标从0开始。
count[]：数组，长度为m，下标从0开始，其中元素count[i]表示机器i运行的任务数。
i：循环变量。
j：循环变量。
k：临时变量。
max：完成所有任务的时间。
min：临时变量。
2.函数schedule
void schedule（ ）{
int i,j,k,max=0;
for(i=0;i＜m;i++){
d[i]=0;
for(j=0;j＜n;j++){
s[i][j]=0;
}
}
for(i=0;i＜m;i++){//分配前m个任务
s[i][0]=i;
(1);
count[i]=1;
}
for((2);i＜n;i++){//分配后n-m个任务
int min=d[0];
k=0;
for(j=1;j＜m;j++){//确定空闲时间
if(min>d[j]){
min=d[j];
k=j;//机器k空闲
}
}
(3);
count[k]=count[k]+1;
d[k]=d[k]+t[i];
}
for(i=0;i＜m;i++){//确定完成所有任务所需要的时间
if((4)){
max=d[i];
}
}
}
【问题1】（8分）
根据说明和C代码，填充C代码中的空（1）~（4）。
【问题2】（2分）
根据说明和C代码，该问题采用了（5）算法设计策略，时间复杂度（6）（用O符号表示）
【问题3】（5分）
考虑实例m=3（编号0~2），n=7（编号0~6），各任务的运行时间为{16，14，6，5，4，3，2}。则在机器0、1和2上运行的任务分别为（7）、（8）和（9）（给出任务编号）。从任务开始运行到完成所需的时间为（10）。
正确答案及解析
正确答案
解析
【问题1】
（1）d[i]=t[i]（2）i=m（3）s[k][count[k]]=i（4）max＜d[i]
【问题2】
（5）贪心（6）O(mn)
【问题3】
（7）0（8）1、5（9）2、3、4、6（10）17
本题考查算法的设计和分析技术中的贪心算法。
贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。
【问题1】
根据上述思想和题中的说明，首先将s[][]和d[]数组初始化为0，然后要做的就是按要求“算法基于最长运行时间作业优先的策略，按顺序先把每个任务分配到一台机器上”，可以推断（1）处为d[i]=t[i]，此后需将剩下的n-m个任务按顺序分配给空闲的机器，故（2）处将i初始化为以m为起始的任务，即i=m，（3）处所在的位置是分配后n-m个任务，在这个过程中，必须要对s矩阵的内容进行修改，但目前已经出的代码没有这个内容，所以此处必然是对s的修改。从对s矩阵的注释可以了解到，s[i][j]表示机器i运行的任务j的编号，此时涉及任务的机器号为k，而待分配的任务i是机器的第count[k]个任务，即s[k][count[k]]=i，（4）处已经完成了任务的运行，此处需要统计所有机器所运行任务的最长时间，对于每个机器i的运行时间为d[i]，存在d[i]大于当前的最大时间Max，就将当前机器的运行时间d[i]赋给Max，即Max＜d[i]。
【问题2】
根据以上分析，（5）处采用了贪心算法的策略，而时间复杂度由算法中的两个嵌套for循环和两个非嵌套for循环确定，即为O(mn)。
【问题3】
根据题中算法的思想将任务的前三个任务分给三个机器，再将接下来的任务分给最先空闲的机器，故可知机器0运行任务0，机器1运行任务1、5，机器3运行任务2、3、4、6；且运行的最长时间为17。
包含此试题的试卷
你可能感兴趣的试题
提供阶段DHCP数据帧中目MAC地址是（5），报文源IP地址是（6）,目IP地址是（7），该报文基于UDP，目端口号是（8）。
- 查看答案
公司为了增加产品网络推销效果，决定使用一款基于邮件广告推送软件，为了避免使用其他服务商邮件服务器发送邮件时被限制情况，因此决定使用公司自己服务器。在仅考虑投资最小化情况下，基于现有IIS web服务器条件下，是否需要购置新邮件服务器软件，并说明理由。
- 查看答案
网络管理员设置了基于windows server 2008 R2服务器上创建了DHCP服务器。公司新购进一批某公司生产同型号机器分配给客户服务部使用，只允许这批机器获取192.168.1.0/24这个地址范围内地址，这个地址范围默认网关是192.168.1.1。问题5 某台机器不能上网，管理员在机器上检查后，发现机器IP设置如下：以太网适配器 本地连接: 连接特定 DNS 后缀 . . . . . . . : 描述. . . . . . . . . . . . . . . : Realtek PCIe GBE Family Controller 物理地址. . . . . . . . . . . . . : 88-51-FB-47-C3-41 DHCP 已启用 . . . . . . . . . . . : 是 自动配置已启用. . . . . . . . . . : 是 IPv4 地址 . . . . . . . . . . . . : 172.16.1.100(首选) 子网掩码 . . . . . . . . . . . . : 255.255.255.0 获得租约时间 . . . . . . . . . : 2018年x月x日 8:59:41 租约过期时间 . . . . . . . . . : 2018年x月x日 10:59:41 默认网关. . . . . . . . . . . . . : 172.16.1.1可能原因是（8）A． 这台机器是用户自己设置了错误静态IP地址导致不能上网B． DHCP服务器上筛选器设置不正确C． 网络中存在非法DHCP服务器D． 用户机器网卡故障解决此问题方法是（9）A. 将客户机器静态IP地址设置为动态获取B. 重新设置服务器上筛选器C. 使用dhcp snooping 限制非法DHCP服务器D. 更换新网卡
- 查看答案
某天管理员接到PCN用户报告，不能正常访问Internet。管理员在该用户机器上使用（15）命令，得到下图所示：
由此可知PCN不能上网原因是（16），解决方法是（17）
- 查看答案
网络管理员设置了基于windows server 2008 R2服务器上创建了DHCP服务器。公司新购进一批某公司生产同型号机器分配给客户服务部使用，只允许这批机器获取192.168.1.0/24这个地址范围内地址，这个地址范围默认网关是192.168.1.1。问题4：为了提高dhcp服务器容错能力和平衡服务器负载，在windowsdhcp服务器中可以使用（6）功能，为了平衡 DHCP 服务器使用，可以采用（7）规则将作用域地址分配给两个 DHCP 服务器。
- 查看答案