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

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

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

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

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

閱讀下列說(shuō)明和C代碼，回答問(wèn)題1和問(wèn)題2，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
某公司購(gòu)買(mǎi)長(zhǎng)鋼條，將其切割后進(jìn)行出售。切割鋼條的成本可以忽略不計(jì)，鋼條的長(zhǎng)度為整英寸。已知價(jià)格表P，其中中Pi（i＝1，2，...，m）表示長(zhǎng)度為i英寸的鋼條的價(jià)格?，F(xiàn)要求解使銷(xiāo)售收益最大的切割方案。
求解此切割方案的算法基本思想如下：
假設(shè)長(zhǎng)鋼條的長(zhǎng)度為n英寸，最佳切割方案的最左邊切割段長(zhǎng)度為i英寸，則繼續(xù)求解剩余長(zhǎng)度為n－i英寸鋼條的最佳切割方案?？紤]所有可能的i，得到的最大收益rn對(duì)應(yīng)的切割方案即為最佳切割方案。rn的遞歸定義如下：
rn=max1≤i≤n(pi+rn-i)對(duì)此遞歸式，給出自頂向下和自底向上兩種實(shí)現(xiàn)方式
【C代碼】
/*常量和變量說(shuō)明
n：長(zhǎng)鋼條的長(zhǎng)度
P[]：價(jià)格數(shù)組
*/
#defineLEN100
intTop＿Down＿Cut_Rod(intP[]，intn)｛/*自頂向下*／Intr=0
Inti；if(n=0){
retum0；
}
for(i=1；（1）；i++){
inttmp=p[i]+Top_Down_Cut_Rod(p，n-i)r=(r>=tmp)?r：tmp；


}
returnr；
}

intBottom_Up_Cut_Road(intp[],intn){/*自底向上*/
intr[LEN]={0};
inttemp=0;
inti,j;
for(j=1;j<=n;j++){
temp=0;
for(i=l;(2);i++){
temp=(3);
}
（4）
}
returnr[n];
}

【問(wèn)題1】（8分）
根據(jù)說(shuō)明，填充C代碼中的空（1）～（4）。
【問(wèn)題2】（7分）
根據(jù)說(shuō)明和C代碼，算法采用的設(shè)計(jì)練略為（5）。
求解時(shí)，自頂向下方法的時(shí)間復(fù)雜度為（6）；自底向上方法的時(shí)間復(fù)雜度為（7）
（用O表示）。
信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/st/396349820.html

信管網(wǎng)考友試題答案分享：

信管網(wǎng)yiren：
i＜=len＜br＞i＜=j＜br＞max（temp，r[i]+r[j-i]）＜br＞r[j]=temp＜br＞分治法＜br＞on2，on2

信管網(wǎng)cnitpm509362975264：
問(wèn)題1： 1；i＜=n 2: i＜=n 3: 4: r[n] ＝ temp 問(wèn)題2： 動(dòng)態(tài)規(guī)劃法 o（nlogn） o（n2）

信管網(wǎng)suhx：
【問(wèn)題1】： （1）：i＜=n，（2）：i＜n-j，（3）：p[i]+bottom_up_cut_road（p,n-j），（4）：r[j]=r[j] ＞ temp ? r[j] : temp， 【問(wèn)題2】： 算法設(shè)計(jì)策略為：分治 自頂向下時(shí)間復(fù)雜度為：o（n的平方） 自底向上時(shí)間復(fù)雜度為：o（n的三次方）

信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/st/396349820.html