答案及解析：[问答题]设有m台完全相同的机器运行n个独立的任务，运行任务i所需的时间为ti，要求确定一个调度方案，使得完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略

问题：

[问答题] 设有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.函数schedulevoid 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）。

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题