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

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

軟件設計師案例分析每日一練試題（2026/5/29）在線測試：m.weidaozhaoqing.com/exam/ExamDayAL.aspx?t1=4&day=2026/5/29

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

軟件設計師案例分析每日一練試題內容（2026/5/29）

某工程計算中經常要完成多個矩陣相乘（鏈乘）的計算任務，對矩陣相乘進行以下說明。
（1）兩個矩陣相乘要求第一個矩陣的列數(shù)等于第二個矩陣的行數(shù)，計算量主要由進行乘法運算的次數(shù)決定，假設采用標準的矩陣相乘算法，計算Amxn*Bnxp需要m*n*p次行乘法運算的次數(shù)決定、乘法運算，即時間復雜度為O（m*n*p）。
（2）矩陣相乘滿足結合律，多個矩陣相乘時不同的計算順序會產生不同的計算量。以矩陣A15×100，A2100*8，A38x50三個矩陣相乘為例，若按（A1*A2）*A3計算，則需要進行5*100*8+5*8*50=6000次乘法運算，若按A1*（A2*A3）計算，則需要進行100*8*50+5*100*50=65000次乘法運算。
矩陣鏈乘問題可描述為：給定n個矩陣，對較大的n，可能的計算順序數(shù)量非常龐大，用蠻力法確定計算順序是不實際的。經過對問題進行分析，發(fā)現(xiàn)矩陣鏈乘問題具有最優(yōu)子結構，即若A1*A2**An的一個最優(yōu)計算順序從第k個矩陣處斷開，即分為A1*A2*…*Ak和Ak+1*Ak+2*...*An兩個子問題，則該最優(yōu)解應該包含 A1*A2*…*Ak的一個最優(yōu)計算順序和 Ak+1*Ak+2*...*An  的一個最優(yōu)計算順序。據此構造遞歸式：

其中，cost[i][j]表示Ai+1*Ai+2*...Aj+1的最優(yōu)計算的計算代價。最終需要求解cost[0][n-1]。
【C代碼】
算法實現(xiàn)采用自底向上的計算過程。首先計算兩個矩陣相乘的計算量，然后依次計算3個矩陣、4個矩陣、…、n個矩陣相乘的最小計算量及最優(yōu)計算順序。下面是該算法的語言實現(xiàn)。
（1） 主要變量說明
n：矩陣數(shù)
seq[]：矩陣維數(shù)序列
cost[i][j]：二維數(shù)組，長度為n*n，其中元素cost[i][j]表示Ai+1*Ai+2**Aj+1的最優(yōu)的計算代價。
trace[][]:二維數(shù)組，長度為n*n，其中元素trace[i][j]表示Ai+1*Ai+2**Aj+1的最優(yōu)計算順序對應的劃分位置，即k。

（2）函數(shù)cmm
#define N100
int cost[N[N];
int trace[N][N];
int cmm(int n,int seq[]){
int tempCost;
int tempTrace;
int i,j,k,p;
int temp;
for( i=0;i for(p=1;p for(i=0; i（1）  ;
tempCost = -1;
for(k = i;  （2） ;k++){
temp=  （3）  ;
if(tempCost==-1 || tempCost>temp){
tempCost = temp;
tempTrace=k;
}
}
cost[i][j] = tempCost;
（4）  ;
}
}
return cost[0][n-1];
}

【問題1】（8分）
根據以上說明和C代碼，填充C代碼中的空（1）～（4）。
【問題2】（4分）
根據以上說明和C代碼，該問題采用了（5）算法設計策略，時間復雜度為（6）（用O符號表示）。
【問題3】（3分）
考慮實例n=4，各個矩陣的維數(shù)為A1為15*5，A2為5*10，A3為10*20，A4為20*25，即維度序列為15，5，10，20和25。則根據上述C代碼得到的一個最優(yōu)計算順序為（7）（用加括號方式表示計算順序），所需要的乘法運算次數(shù)為 （8）。

信管網試題答案與解析：m.weidaozhaoqing.com/exam/ExamDayAL.aspx?t1=4&day=2026/5/29

信管網考友試題答案分享：

信管網試題答案與解析：m.weidaozhaoqing.com/exam/ExamDayAL.aspx?t1=4&day=2026/5/29