(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为tI,要求确定一个调度方案,使得完成所有任务所需要的时间最短。

admin2018-07-27  33

问题 (2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
    【说明】
    设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为tI,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
    假设任务已经按照其运行时间从大到小排序,算法基于最长运行时间作业优先的策略;按顺序先把每个任务分配到一台机器上,然后将剩余的任务一次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
m:机器数
n:任务数
t[]:输入数组,长度为n,其中每个元素表示任务的运行时间,下标从0开始
S[][]:二维数组,长度为m~n,下标从0开始,其中元素sD]表示机器i运行的任务
j的编号
d[]:数组,长度为m,其中元素d表示机器i的运行时间,下标从0开始
count[]:数组,长度为m,下标从0开始,其中元素count表示机器i运行的任务数
i:循环变量
j:循环变量
k:临时变量
max:完成所有任务的时间
min:临时变量
(2)函数schedule
void  Schedule(){
    int i,j,k,max=0;
    for(i=0;i<m;i++){
    d=0;
    for(j=0;j<n;j++){
    s[j]=0;
    }
}
    for(i=0;i<m;i++){    //分配前m个任务
    s[0]=i;
    ______(1)
    count=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;
    for(i=0;i<m;i++){    //确定完成所有任务所需要的时间
    if(____(4){
    max=d;
    }
         }
        }
    }
根据说明和C代码,填充C代码中的空(1)~(4)。

选项

答案(1)d[i]=d[i]+t[i](2)i=m(k)s[k][0]=i(4)max<d[i]

解析 本题考查算法的设计和分析技术中的贪心算法。
    贪心算法是一种不追求最优解,只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解,因为它省去了为找到最优解要穷尽所有可能而必须耗费的大量时间。贪心算法常以当前情况为基础做出最优选择,而不考虑各种可能的整体情况,所以贪心算法不要回溯。
    根据上述思想和题中的说明,首先将s[][]和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<d
转载请注明原文地址:https://jikaoti.com/ti/UFi7FFFM
0

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