阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 在一块电路板的上下两端分别有n个接线柱。根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱Ⅱ(i)相连,称其为该电路板上的第i条连线。如图4.1所示的π(i)排列

admin2017-09-13  38

问题 阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
在一块电路板的上下两端分别有n个接线柱。根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱Ⅱ(i)相连,称其为该电路板上的第i条连线。如图4.1所示的π(i)排列为{8,7,4,2,5,1,9,3,10,6}。对于任何l≤iπ(j)。
在制作电路板时,要求将这n条连线分布到若干绝缘层上,在同一层上的连线不相交。现在要确定将哪些连线安排在一层上,使得该层上有尽可能多的连线,即确定连线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。

【分析问题】
记N(i,j)={t|(t,n(t))~Nets,t≤i,7c(t)≤j)。N(i,j)的最大不相交子集为MNS(i,j),size(i,j)=IMNS(i,j)|。
经分析,该问题具有最优子结构性质。对规模为n的电路布线问题,可以构造如下递归式:

【C代码】
下面是算法的C语言实现。
(1)变量说明
size[j]:上下端分别有i个和j个接线柱的电路板的第一层最大不相交连接数
pi:π(i),下标从1开始
(2)C程序
#include“stdlib”
  #include
  #define  N  1 0    /*问题规模*/
  int m=0;    /*记录最大连接集合中的接线柱*/
  void maxNum(int pi[],int si ze IN+1][N+1],int n)  {  /*求最大不相交
  连接数*/
    int i,j;
    for(j=0;j    for(j:pi[1];j<=n;j++) (1);    /*当j>=π(1)时*/
    for(i=2;i    for(j=0;j;j++)  (2) ;    /*当j时*/
    for(j=pi;j<=n;j++)  {  /*当j>=C时,考虑两种情况*/
    size[j]=size[i一1][j]>=size[i一1][pi一1]+l?size[i一1][j]:
    size[i一1][pi一1]+1;
    }
    }
    /*最大连接数*/
    size[n][n]  =size[n一1][n]  >=si ze[n一1][pi[n]一1]+1?  size[n一1][n]:
    si ze[n一1][pi[n]一1]+1;
    }
/*构造最大不相交连接集合,net表示最大不相交子集中第i条连线的上端接线柱的序号*/
    void constructSet(int pi[],  int  size[N+  1][N+  1],  int n,  int net[n]}  {
    int  i,  j=n;
    m=0;
    for(i=n;i>1;i一一)    {    /*从后往前*/
    if(size[j]!=size[i一1][j]){  /*(i,pi)是最大不相交子集的一条连线*/
    (3)    ;    /*将i记录到数组net中,连接线数自增1*/
    j=pi-1;    /*更新扩展连线柱区间*/
    }
    }
    if(j  >=pi[1])    net[m++]  =1;    /*当i=1时*/
    }
根据以上说明和C代码,填充C代码中的空(1)~(3)。

选项

答案(1)size[1][j]=1 (2)size[i][j]=size[i-1][i] (3)net[m++]=i或其等价形式

解析 本题考查算法设计和C语言实现算法的能力。
本题要求考试对常用的算法设计策略,包括分治法、动态规划、贪心算法、回溯法等有基本的掌握,并理解每类算法策略中的几个典型实例。
一般不要求考生设计问题的求解算法,但要求考生能够理解题目给出的算法设计思路,并补充C程序。如本题中的空(1),可以根据题干中递归式第一部分和C代码中的注释,得到答案size[1][j]=1。

空(2)则根据阅读题干中递归式第二部分和C代码中的注释,得到答案size[j]=size[i-1]

空(3)则依据C代码中的注释,即可得到答案net[m++]=i。
转载请注明原文地址:https://jikaoti.com/ti/yMi7FFFM
0

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