(2012年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在

admin2018-07-27  31

问题 (2012年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
    【说明】
    用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业,在B上处理时间长。一台处理机在某个时刻只能处理一个作业,而且作业处理是不可中断的,每个作业只能被处理一次。现要找出一个最优调度方案,使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
    算法步骤:
    (1)确定候选解上界为R短的单台处理机处理所有作业的完成时间m,有

    (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      }
      }
    }
    printf(’’\n%d\n’’,max);
}
void main(){read();schedule();write();}
根据以上C代码,算法的时间复杂度为_____(6)(用O符号表示)。

选项

答案O(m2n)

解析 从程序的循环层数即可看出算法的时间复杂度。程序的最高循环层数为3层。最外层循环变量的变化范围是1~n-1,次外层循环变量的变化范围是0~m,内层循环变量的变化范围是0~m,所以时间复杂度为O(m2n)。
转载请注明原文地址:https://kaotiyun.com/show/S7DZ777K
0

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