信管网每日一练

软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2022/1/8）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2022/1/8

点击查看：更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容（2022/1/8）

[试题4]

阅读下列说明和C代码，回答下列问题。

[说明]

用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。算法步骤如下。

11确定候选解上界为R短的单台处理机处理所有作业的完成时间m，

12用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)(‖表示逻辑或操作)。

13得到最短处理时间为min(max(x,y))。

[C代码]

下面是该算法的C语言实现。

11常量和变量说明

n：作业数

m：候选解上界

a：数组，长度为n，记录n个作业在A上的处理时间，下标从0开始

b：数组，长度为n，记录n个作业在B上的处理时间，下标从0开始

k：循环变量

p：三维数组，长度为(m+1)*(m+1)*(n+1)

temp：临时变量

max：最短处理时间

12C代码

#include＜stdio.h＞

int  n,  m;

int a[60], b[60], p[100] [100] [60];

void read16 { …… /*输入n、 a、 b, 求出m, 代码略*/

void schedule16 {       /*求解过程*/

int  x, y, k;

for (x=0;x＜=m;x++){

for (y=0;y＜m;y++){

______

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)

______;

if(______)

p[x] [y] [k]=(p[x] [y] [k] ‖ p[x] [y-b[k-1]] [k-1]);

}

}

}

}

void write16 {   /*确定最优解并输出*/

int x, y, temp, max=m;

for (x=0;x＜=m;x++) {

for (y=0,y＜=m;y++){

if(______)

temp______:

if (temp＜max) max = temp;

}

}

}

print ("\n%d\n",max) ;

}

void main16 {

read16 ;

schedule16 ;

write16 ;

}

[问题1]

根据以上说明和C代码，填充C代码中的空缺处。

[问题2]

根据以上C代码，算法的时间复杂度为______(用O符号表示)。

[问题3]

考虑6个作业的实例，各个作业在两台处理机上的处理时间如表2-7所示。该实例的最优解为______，最优解的值(即最短处理时间)为______。最优解用(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上处理。

表2-7 各个作业在两台处理机上的处理时间