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

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

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

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

軟件設計師案例分析每日一練試題內容（2024/2/6）

試題四(15分)
閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對應欄內。
【說明】
某工程計算中要完威多個矩陣相乘（鏈乘）的計算任務。
兩個矩陣相乘要求第—個矩陣的列數等于第二個矩硨的行數，計算量主要由進行乘法運算的次數決定。采用標準的矩陣相乘算法，計算 ，需要m*n*p乘法運算。
矩陣相乘滿足結合律，多個矩陣相乘，不同的計算順序會產生不同的計算量。以矩陣 三個矩陣相乘為倒，若按（A1*A2）*A3計算，則需要進行10*100*5+10*5*50=7500次乘法運算；若按A1*( A2*A3)計算，則需要進行100*5*50+10*100*50=75000次乘法運算?？梢姴煌挠嬎沩樞驅τ嬎懔坑泻艽蟮挠绊?。
矩陣鏈乘問題可描述為：給定n個矩陣，矩陣Ai的維數為 其中i=1,2……n。確定一種乘法順序，使得這n個矩陣相乘時進行乘法的運算次數最少。
由于可能的計算順序數量非常龐大，對較大的n，用蠻力法確定計算順序是不實際的。經過對問題進行分析，發(fā)現(xiàn)矩陣鏈乘問題具有最優(yōu)子結構，即若A1*A2*…*An的一個最優(yōu)計算順序從第k個矩陣處斷開，即分為A1*A2*…* Ak
和Ak+l *Ak+2*…*An兩個子問題，則該最優(yōu)解應該包含A1*A2*…*Ak的一個最優(yōu)計算順序和Ak+l*Ak+2*…* An的一個最優(yōu)計劃順序。據此構造遞歸式，其中，cost[i][j]表示

【C代碼】
算法實現(xiàn)采用自底向上的計算過程。首先計算兩個矩陣相乘的計算量，然后依次計算3個矩陣、4個矩陣、…、n個矩陣相乘的最小計算量及最優(yōu)計算順序。下面是算法的C語言實現(xiàn)。
（1）主要變量說明
n：矩陣數
seq[]：矩陣維數序列
cost[][]：二維數組，長度為n*n，其中元素cost[i][j]表示Ai+1*Ai+2*…*Aj+l的最優(yōu)計算的計算代價
trace[][]：二維數組，長度為n*n，萁中元素trace[i][j]表示Ai+1*Ai+2 *Aj+1的最優(yōu)計算對應的劃分位置，即k
<2)函數cmm
#define N 100
intcost[N][N]
inttrace[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=l;pfor(i=0;(1) ;i++{
(2);
tempCost=-1;
for(k = i;ktemp= (3);
if(tempCost==-l||tempCost>temp){
tempCost=temp;
(4);
}
}
Cost[i][j]=tempCost;
trace[i][j] = tempTrace;
}
}
return cost[O][n-l];
}
【問題1】（8分）
根據以上說明和C代碼，填充C代碼中的空(1)~(4)。
【問題2】（4分）
根據隊上說明和C代碼，該問題采用了(5)算法設計策略，時間復雜度(6)。（用〇符號表示）
【問題3】（3分）
考慮實例n=6，各個矩陣的為數：A1為5*10，A2為10*3，A3為3*12，A4為12*5，A5為5*50，A6為50*6，即維數序列為5，10，3，12，5，50，6。則根據上述C代碼得到的一個最優(yōu)計算順序為(7) （甩加括號方式表示計算順序），所需要的乘法運算次數為(8)。