軟件設(shè)計師案例分析當天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計師案例分析每日一練試題（2024/4/20）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/4/20

點擊查看：更多軟件設(shè)計師習題與指導

軟件設(shè)計師案例分析每日一練試題內(nèi)容（2024/4/20）

試題四（共15分）
閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對應欄內(nèi)。
【說明】
在一塊電路板的上下兩端分別有n個接線柱。根據(jù)電路設(shè)計，用(i,π(i))表示將上端接線柱i與下端接線柱π(i)相連，稱其為該電路板上的第i條連線。如圖4-1所示的π(i)排列為{8,7,4,2,5,1,9,3,10,6}。對于任何1≤iπ(j)。



在制作電路板時，要求將這n條連線分布到若干絕緣層上，在同一層上的連線不相交?，F(xiàn)在要確定將哪些連線安排在一層上，使得該層上有盡可能多的連線，即確定連線集Nets={(i,π(i))，1≤i≤n}的最大不相交子集。
【分析問題】
記N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}。N(i,j)的最大不相交子集為MNS(i,j)，size(i,j)=|MNS(i,j)|。
經(jīng)分析，該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對規(guī)模為n的電路布線問題，可以構(gòu)造如下遞歸式：



【C代碼】
下面是算法的C語言實現(xiàn)。
（1）變量說明
size[i][j]：上下端分別有i個和j個接線柱的電路板的第一層最大不相交連接數(shù)
pi[i]：π(i)，下標從1開始
（2）C程序
#include"stdlib.h"
#include
#define N 10/*問題規(guī)模*/
Int m=0；/*牢記錄最大連接集合中的接線柱*/
Void maxNum(intpi[],intsize[N+1][N+1],intn){/*求最大不相交連接數(shù)*/
int i,j;
for(j=0;j for(j=pi[i];j<=n;j++)（1）;/*當j>=π(1)時*/
for(i=2;ifor(j=0;j for(j=pi[i];j<=n；j++){/*當j>=c[i]時,考慮兩種情況*/
size[i][j]=size[i-l][j]>=size[i-l][pi[i]-l]+1?size[i-l][j]:size[i-l][pi[i]-l]+l;
}
}
/*最大連接數(shù)*/
size[n][n]=size[n-l][n]>=size[n-l][pi[n]-l]+1?size[n-l][n]:size[n-l][pi[n]-l]+l;
}
/*構(gòu)造最大不相交連接集合，net[i]表示最大不相交子集中第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[i][j]!=size[i-l][j]){/*(i,pi[i])是最大不相交子集的一條連線*/
（3）;/*將i記錄到數(shù)組net中，連接線數(shù)自增1*/
j=pi[i]-1;/*更新擴展連線柱區(qū)間*/
}
}
if(j>=pi[l])net[m++]=l;/*當i=1時*/
}
?【問題1】（6分）
根據(jù)以上說明和C代碼，填充C代碼中的空（1）~（3）。
?【問題2】（6分）
根據(jù)題干說明和以上C代碼，算法采用了（4）算法設(shè)計策略。
函數(shù)maxNum和constructSet的時間復雜度分別為（5）和（6）（用O表示）。
?【問題3】（3分）
若連接排列為{8,7,4,2,5,1,9,3,10,6}，即如圖4-1所示，則最大不相交連接數(shù)為（7），包含的連線為（8）（用(i,π(i))的形式給出）。

信管網(wǎng)過去立馬翻篇：
＜br /＞＜img src=＂http://pic.cnitpm.com/upload/2023/04/tbimg/04-14/1681482305.jpg＂ /＞

信管網(wǎng)cnitpm603660373945：
if （i == 1）{ size[1][j] == 0； }else { size[i][j] == 1； } （4）動態(tài)規(guī)劃 （5）o（n） ＝ n^2 log2^n