軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：www.jazzmuze.com/exam/ExamDayAL.aspx?t1=4

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

軟件設(shè)計(jì)師案例分析每日一練試題（2025/4/14）在線(xiàn)測(cè)試：www.jazzmuze.com/exam/ExamDayAL.aspx?t1=4&day=2025/4/14

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

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

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

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