2. 计算机
  3. 阅读下列说明和C代码，回答以下问题，将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间

阅读下列说明和C代码，回答以下问题，将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间

admin2013-07-09  52
问题 阅读下列说明和C代码，回答以下问题，将解答写在答题纸的对应栏内。
【说明】
    用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
    算法步骤：
    (1)确定候选解上界为R段的单台处理机处理所有作业的完成时间m：
   
    (2)用p(x，y，k)=1表示前志个作业可以在A用时不超过z且在B用时不超过y时间内处理完成，则p(x，y，k)=p(x一ak，y，k一1)||p(x，y一bk，k一1)(||表示逻辑或操作)。
    (3)得到最短处理时间为min(max(z，y))。
    【C代码】
    下面是该算法的C语言实现。
    (1)常量和变量说明
    n：作业数
    m：候选解上界
    n：数组，长度为n，记录n个作业在A上的处理时间，下标从0开始
    b：数组，长度为n，记录n个作业在B上的处理时间，下标从0开始
    k：循环变量
    p：三维数组，长度为(m+1)*(m+1)*(n+1)
    temp：临时变量
    max：最短处理时间
    (2)C代码
    #include    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             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()；}
根据以上C代码，算法的时间复杂度为  (6)  (用O符号表示)。
选项
答案(6)O(m2n)
解析 从程序的循环层数即可看出算法的时间复杂度。程序的最高循环层数为3层。最外层循环变量的变化范围是1～n一1，次外层循环变量的变化范围是0～m，内层循环变量的变化范围是0～m，所以时间复杂度为０(m2n)。
转载请注明原文地址:https://kaotiyun.com/show/miDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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