阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为t
i
,要求确定一个调度方案,使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序,算法基于最长运行时间作业优先的策略;按顺序先把每个任务分配到一台机器上,然后将剩余的任务一次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
m:机器数
n:任务数
t[]:输入数组,长度为n,其中每个元素表示任务的运行时间,下标从0开始
s[][]:二维数组,长度为m*n,下标从oF始,其中元素s[i][i]表示机器i运行的任j的编号
d[]:数组,长度为m其中元素d[i]表示机器i的运行时间,下标从0开始
count[]:数组,长度为m,下标从0开始,其中元素count[i一]表示机器i运行的任务数
i:循环变量
i:循环变量
k:临时变量
max:完成所有任务的时间
min:临时变量
(2)函数schedule
void schedule(){
int i,j,k max=0;
for(i=0;id[j])(
( min:d[j];
k=j; //机器k空闲
}
}
(3) ;
count[k]=count[k]+1;
d[k]=d[k]+t[i];
for(i=0;i
【正确答案】正确答案:(1)d[i]=d[i]+t[i](2)i=m(3)s[k][0]=i(4)Max
【答案解析】
问答题
根据说明和C代码,该问题采用了(5)算法设计策略,时间复杂度为(6)(用O符号表示)
【正确答案】正确答案:(5)贪心(6)0(2m*n+2m)
【答案解析】
问答题
考虑实例m=3(编号0~2),n=7(编号0~6),各任务的运行时间为{16,14,6,5,4,3,2}。则在机器0、1和2上运行的任务分别为(7)、(8)和(9)(给出任务编号)。从任务开始运行到完成所需要的时间为(10)。
【正确答案】正确答案:(7)0(8)1、5(9)2、3、4、6(10)17
【答案解析】解析:本题考查算法的设计和分析技术中的贪心算法。贪心法是一种不追求最优解,只希望得到较为满意解的方法。贪心法一般可以快速得到满意的解,因为省去了为找到最优解要穷尽所有可能而必须耗费的大量时间。贪心法常以当前情况为基础做出最优选择,而不考虑各种可能的整体情况,所以贪心法不要回溯。问题1:根据上述思想和题中的说明,首先将s[1[]和d[]数组初始化为0,然后将前m个运行时间最长的任务分给m个机器,(1)中需要表示此时每个机器运行的时间,即当前已经运行的时间加上此时所运行任务的时间,可以推断(1)处为d[i]=d[i]+t[i],此后需将剩下的n—m个任务按顺序分配给空闲的机器,故(2)处将i初始化为以m为起始的任务,即i=m,(3)处根据空闲的机器分配任务,所以需记录第k个空闲机器所运行任务的编号,即s[k][0]=i,(4)处已经完成了任务的运行,此处需要统计所有机器所运行任务的最长时间,对于每个机器i的运行时问为d[i],存在d[i]大于当前的最大时间Max,就将当前机器的运行时间d[i]赋给.Max,即Max