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