2. 计算机
  3. 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案，使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序，算法基

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案，使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序，算法基

admin2014-11-13  59
问题 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案，使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略；按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
m：机器数
n：任务数
t[]：输入数组，长度为n，其中每个元素表示任务的运行时间，下标从0开始
s[][]：二维数组，长度为m*n，下标从oF始，其中元素s表示机器i运行的任j的编号
d[]：数组，长度为m其中元素d表示机器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    d=0；
    for(j=0；j    s[j]=0；
    }
    }
    for(i：0；i    S[0]=i；
    (1)；
  count=1；
  for((2)    ；i    int min：d[0]；
    k=0：
    for(J=1；J    i f(min>d[j])(
    min：d[j]；
    k=j；    ／／机器k空闲
    }
    }
    (3) ；
    count[k]=count[k]+1；
    d[k]=d[k]+t；
    for(i=0；i    i f(   (4)   )(
    max：d；
    }
    }
    }
    }
考虑实例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=d+t，此后需将剩下的n—m个任务按顺序分配给空闲的机器，故(2)处将i初始化为以m为起始的任务，即i=m，(3)处根据空闲的机器分配任务，所以需记录第k个空闲机器所运行任务的编号，即s[k][0]=i，(4)处已经完成了任务的运行，此处需要统计所有机器所运行任务的最长时间，对于每个机器i的运行时问为d，存在d大于当前的最大时间Max，就将当前机器的运行时间d赋给．Max，即Max。问题2：根据以上分析，(5)处采用了贪心算法的策略，而时间复杂度由算法中的两个嵌套for循环和两个非嵌套for循环确定，即为O(2m*n+2m)，问题3：根据题中算法的思想将前三个任务分给三个机器，再将接下来的任务分给最先空闲的机器，故可知机器O运行任务0，机器1运行任务1、5，机器2运行任务2、3、4、6；且运行的最长时间为17。
转载请注明原文地址:https://kaotiyun.com/show/9pDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)