首页
登录
从业资格
设有m台完全相同的机器运行n个独立的任务,运行任务i所需的时间为ti,要求确定一
设有m台完全相同的机器运行n个独立的任务,运行任务i所需的时间为ti,要求确定一
题库
2022-08-02
61
问题
设有m台完全相同的机器运行n个独立的任务,运行任务i所需的时间为ti,要求确定一个调度方案,使得完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序,算法基于最长运行时间作业优先的策略,按顺序先把每个任务分配到一台机器上,然后将剩余的任务依次放入最先空闲的机器。【C代码】下面是算法的C语言实现。1.常量和变量说明m:机器数n:任务数t[]:输入数组,长度为n,下标从0开始,其中每个元素表示任务的运行时间,下标从0开始。s[][]:二维数组,长度为m*n,下标从0开始,其中元素s
[j]表示机器i运行的任务j的编号。d[]:数组,长度为m其中元素d
表示机器i的运行时间,下标从0开始。count[]:数组,长度为m,下标从0开始,其中元素count
表示机器i运行的任务数。i:循环变量。j:循环变量。k:临时变量。max:完成所有任务的时间。min:临时变量。2.函数schedulevoid 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
;}}}【问题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)。
选项
答案
解析
【问题1】
(1)d
=t
(2)i=m(3)s[k][count[k]]=i(4)max<d
【问题2】
(5)贪心(6)O(mn)
【问题3】
(7)0(8)1、5(9)2、3、4、6(10)17
本题考查算法的设计和分析技术中的贪心算法。
贪婪算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。
【问题1】
根据上述思想和题中的说明,首先将s[][]和d[]数组初始化为0,然后要做的就是按要求“算法基于最长运行时间作业优先的策略,按顺序先把每个任务分配到一台机器上”,可以推断(1)处为d
=t
,此后需将剩下的n-m个任务按顺序分配给空闲的机器,故(2)处将i初始化为以m为起始的任务,即i=m,(3)处所在的位置是分配后n-m个任务,在这个过程中,必须要对s矩阵的内容进行修改,但目前已经出的代码没有这个内容,所以此处必然是对s的修改。从对s矩阵的注释可以了解到,s
[j]表示机器i运行的任务j的编号,此时涉及任务的机器号为k,而待分配的任务i是机器的第count[k]个任务,即s[k][count[k]]=i,(4)处已经完成了任务的运行,此处需要统计所有机器所运行任务的最长时间,对于每个机器i的运行时间为d
,存在d
大于当前的最大时间Max,就将当前机器的运行时间d
赋给Max,即Max<d
。
【问题2】
根据以上分析,(5)处采用了贪心算法的策略,而时间复杂度由算法中的两个嵌套for循环和两个非嵌套for循环确定,即为O(mn)。
【问题3】
根据题中算法的思想将任务的前三个任务分给三个机器,再将接下来的任务分给最先空闲的机器,故可知机器0运行任务0,机器1运行任务1、5,机器3运行任务2、3、4、6;且运行的最长时间为17。
转载请注明原文地址:https://tihaiku.com/congyezige/2410316.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
系统规划的主要任务包括()。A.明确组织的信息需求,制定系统总体结构方案 B
系统日常操作日志应该为关键性的运作提供审核追踪记录,并保存合理时间段。利用日志工
以下①~⑥中属于项目管理知识领域的是()。①项目范围管理②项目时间管理③项目成
以下关于进度管理工具甘特图的叙述中,不正确的是()。A.能清晰地表达每个任务的
在做好人力资源规划的基础上,__()__是IT部门人力资源管理更为重要的任务。
现代企业对信息处理不仅要求及时,而且要准确反映实际情况。所以,信息准确性还包括的
若磁盘的转速提高一倍,则()A.平均存取时间减半 B.平均寻道时间加倍
某项目主要由A~I任务构成,其计划图(如下图所示)展示了各任务之间的前后关系以及
某指令流水线由5段组成,第1、3、5段所需时间为Δt,第2、4段所需时间分别为3
如果某一事务程序的运行导致服务器重新启动,这类故障属于系统故障,恢复过程中需要根
随机试题
但那时我年少,血旺气盛,誓与凡俗抗争到底,于是连哄带骗将一净高1.74米女孩拐回家做起了太太,这一壮举颇为“残废”们扬了一段眉吐了半口气。将太太置
唐三彩(TangTri-coloredGlazedPottery)是唐代彩色釉陶器(color一glazedpottery)的总称,它的釉色包括
大众教育
为了切实做到尊重患者自主性决定,医生向患者提供信息时要避免()A.适度
吸入麻醉药相关肝损害最严重的是:A.氟烷 B.恩氟醚 C.异氟醚 D.七氟
在分部分项工程成本分析中,预算成本的资料来自()。A、施工任务单的实际工程量
A.血府逐瘀汤 B.柴胡疏肝散 C.一贯煎 D.龙胆泻肝汤 E.膈下逐瘀
从ABC公司去年年末的资产负债表、利润表及相关的报表附注中可知,该公司去年利
用在其他吊装方法不便或不经济的场合,重量不大、跨度、高度较大的场合,如桥梁建造、
以下关于实物资产清查方法的表述中,正确的有()。A、实物资产常用的清查方法主要有
最新回复
(
0
)