【软件设计师真题】下午题第四大题---算法设计
系列文章目录
1.【软考之软件设计师】PPT课件
2.【软考之软件设计师】学习笔记
3.【软件设计师真题】下午题第一大题—数据流图设计
4.【软件设计师真题】下午题第二大题—数据库设计
5.【软件设计师真题】下午题第三大题—UML 分析与设计
6.【软件设计师真题】下午题第四大题—算法设计
7.【软件设计师真题】下午题第五大题—面向对象程序设计
常用的算法设计技术主要有迭代法、穷举搜索法、递推法、递归法、回溯法、贪心法、分治法、动态规划法等。递归法、回溯法及贪心法极为重要，要重点掌握。
一、真题一
1、题目
阅读下列说明和 C 代码，回答问题 1~问题 3，将解答写在答题纸的对应栏内。
【说明】
设有 m 台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为t，要求确定一个调度方案，使得完成所有任务所需要的时间最短。
假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略:按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。
【C 代码】
下面是算法的 C 语言实现。
(1)常量和变量说明。
m:机器数。
n:任务数。
t[]:输入数组，长度为n，其中每个元素表示任务的运行时间，下标从0开始。s[][]:二维数组，长度为 mxn，其中元素 s[i][i]表示机器i运行的任务ì的编号，下标从0开始。
d[]:数组，长度为 m，其中元素 d[]表示机器i的运行时间，下标从0开始。
count[]:数组，长度为 m，其中元素 count[i]表示机器i运行的任务数，下标从0开始。
i:循环变量。
j:循环变量。
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;(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)。
2、解析
本题考查算法的设计和分析技术中的贪心算法，
贪心算法是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解要穷尽所有可能而必须耗费的大量时间。贪心算法常以当前情况为基础做出最优选择，而不考虑各种可能的整体情况，所以贪心算法不需要回溯。
【问题1】
根据上述思想和题中的说明，首先将s[][]和d[]数组初始化为0，然后将前m个运行时间最长的任务分给m个机器，空(1)处需要表示此时每个机器运行的时间，即当前已经运行的时间加上此时所运行任务的时间，可以推断空(1)处应填入d[i]=d[i]+t[i]。此后需将剩下的n-m个任务按顺序分配给空闲的机器，故空(2)处将i初始化为以m为起始的任务，即空(2)处应填入i-m。空(3)处根据空闲的机器分配任务，所以需记录第k个空闲机器所运行任务的编号，即空(3)处应填入s[k][0]-ī。空(4)处已经完成了任务的运行，此处需要统计所有机器所运行任务的最长时间，机器i的运行时间为d[i]，若有d[i]大于当前的最大时间max，就将当前机器的运行时间d[i]赋给max，即空(4)处应填入Max<d[i]。
【问题2】
根据以上分析，该问题采用了贪心算法的策略，而时间复杂度由算法中的两个嵌套for循环和两个非嵌套 for 循环确定，即为 O(2m*n+2m)。
【问题3】
根据题中算法的思想，将前三个任务分给三个机器，再将接下来的任务分给最先空闲的机器，故可知机器0运行任务 0，机器1运行任务1、5，机器 2运行任务 2、3、4、6,且运行的最长时间为 17。
3、答案
【问题1】
(1)d{i]=d{i]+t[i]。
(2)i=m。
(3)s[k][0]=i.
(4) max < d[i].
【问题 2】
(5)贪心。
(6)O(2m*n+2m).
【问题3】
(7)0.
(8)1、5。
(9)2、3、4、6.
(10)17.