答案及解析：[问答题]用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处

问题：

[问答题] 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间（所有作业被处理的时间之和）最少。算法步骤：（1）确定候选解上界为最短的单台处理机处理所有作业的完成时间m，中级软件设计师,历年真题,2012年上半年（下午）《软件设计师》真题

（2）用p（x，y，k）=1表示前k个作业可以在A用时不超过x且在B用时不超过y时间内处理完成，则p（x，y，k）=p（x-ak，y，k-1）||p（x，y-bk，k-1）（||表示逻辑或操作）。（3）得到最短处理时问为min（max（x，y））。【C代码】下面是该算法的C语言实现。（1）常量和变量说明n:作业数m:候选解上界a:数组，长度为n，记录n个作业在A上的处理时间，下标从0开始b:数组，长度为n，记录n个作业在B上的处理时间，下标从0开始k:循环变量p:三维数组，长度为（m+1）*（m+1）*（n+1）temp:临时变量max:最短处理时间（2）C代码#include＜stdio.h>int n，m;int a[60]，b[60]，p[100][100][60];void read（　　）{/*输入n、a、b，求出m，代码略*/}void schedule（　　）{/*求解过程*/int x，y，k;for（x=0；x＜=m；x++）{for(y=0；y＜m；y++）{（1）for（k=1；k＜n；k++）p[x][y][k]=0；}}for（k=1；k＜=n；k++）{for（x=0；x＜=m；x++）{for（y=0；y＜=m；y++）{if（x-a[k-1]>=0）（2）；if（（3））p[x][y][k]=(p[x][y][k]||p[x][y-b[k-1]][k-1]);}}}}void write（　　）{/*确定最优解并输出*/int x，y，temp，max=m;for（x=0；x＜=m；x++）{for（y=0;y＜=m;y++）{if(（4））{temp=（5）；if（temp＜max）max=temp;}}}printf(“\n%d\n”，max），}void main（　　）{read（　　）;schedule（　　）;write（　　）;}【问题1】（9分）根据以上说明和C代码，填充C代码中的空（1）～（5）。【问题2】（2分）根据以上C代码，算法的时间复杂度为（6）（用O符号表示）。【问题3】（4分）考虑6个作业的实例，各个作业在两台处理机上的处理时间如表4-1所示。该实例的最优解为（7），最优解的值（即最短处理时间）为（8）。最优解用（x1，x2，x3，x4，x5，x6）表示，其中若第i个作业在A上处理，则xi=1，否则xi=2。如（1，1，1，1，2，2）表示作业1，2，3和4在A上处理，作业5和6在B上处理。表4-1 中级软件设计师,历年真题,2012年上半年（下午）《软件设计师》真题

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

答案解析：

╋纠错

您可能感兴趣的问题