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

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

admin2017-09-13  40
问题 阅读下列说明和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代码，算法采用了(4)算法设计策略。
函数maxNum和constructSet的时间复杂度分别为(5)和(6)(用O表示)。
选项
答案(4)动态规划 (5)O(n2) (6)O(n)
解析 题干在叙述过程中，较明显的提到了动态规划策略的几个特点，如最优子结构，递归式，自底向上求解等，因此这是一个动态规划算法。算法的时间复杂度分析也较简单。函数maxNum中有两重循环，时间复杂度为O(n2)。函数constructSet中有一重循环，时间复杂度为O(n)。
转载请注明原文地址:https://jikaoti.com/ti/JMi7FFFM
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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