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

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

軟件設計師案例分析每日一練試題（2025/3/10）在線測試：www.ichunya.com/exam/ExamDayAL.aspx?t1=4&day=2025/3/10

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

軟件設計師案例分析每日一練試題內容（2025/3/10）

閱讀下列說明和C代碼，回答問題1和問題2，將解答填入答題紙的對應欄內。
【說明】
某公司購買長鋼條，將其切割后進行出售。切割鋼條的成本可以忽略不計，鋼條的長度為整英寸。已知價格表P，其中中Pi（i＝1，2，...，m）表示長度為i英寸的鋼條的價格?，F(xiàn)要求解使銷售收益最大的切割方案。
求解此切割方案的算法基本思想如下：
假設長鋼條的長度為n英寸，最佳切割方案的最左邊切割段長度為i英寸，則繼續(xù)求解剩余長度為n－i英寸鋼條的最佳切割方案。考慮所有可能的i，得到的最大收益rn對應的切割方案即為最佳切割方案。rn的遞歸定義如下：
rn=max1≤i≤n(pi+rn-i)對此遞歸式，給出自頂向下和自底向上兩種實現(xiàn)方式
【C代碼】
/*常量和變量說明
n：長鋼條的長度
P[]：價格數組
*/
#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];
}

【問題1】（8分）
根據說明，填充C代碼中的空（1）～（4）。
【問題2】（7分）
根據說明和C代碼，算法采用的設計練略為（5）。
求解時，自頂向下方法的時間復雜度為（6）；自底向上方法的時間復雜度為（7）
（用O表示）。
信管網試題答案與解析：www.ichunya.com/exam/ExamDayAL.aspx?t1=4&day=2025/3/10

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

信管網cnit**************：
＜div class=＂box＂＞＜span style=＂color:#003399＂＞cnitpm630501712623的原帖： ＜/span＞＜span style=＂color:#999999＂＞2023/5/25 22:11:43＜/span＞＜br＞＜span class=＂style5＂＞【問題1】 1. i ＜= n 2.l ＜= j 3. p[l] + temp 4. p[j] ＝ temp 【問題2】 動態(tài)規(guī)劃，o（nlogn），o（n^2）＜/span＞＜/div＞遞歸是指數級，不可能比自底向上還快，所以不是nlogn 而是 2的n次方

信管網cnit**************：
【問題1】 1. i ＜= n 2.l ＜= j 3. p[l] + temp 4. p[j] ＝ temp 【問題2】 動態(tài)規(guī)劃，o（nlogn），o（n^2）

信管網cnit**************：
【問題1】 1. i ＜= n 2.l ＜= j 3. p[l] + temp 4. p[j] ＝ temp 【問題2】 動態(tài)規(guī)劃，o（nlogn），o（n^2） 【問題3】

信管網cnit**************：
i＜=n i＜=j temp＞=r[i]+r[j-i]?temp:r[i]+r[j-i]； r[j]=temp＞p[j]?temp:p[j] 動態(tài)規(guī)劃 2^n n^2

信管網cnit**************：
【問題1】 1. i ＜= n 2. i ＜= j 3. bottom_up_cut_road（p,n） + temp 4. r[i] ＝ temp 【問題2】 遞歸，o（nlogn），o（n^2）

信管網試題答案與解析：www.ichunya.com/exam/ExamDayAL.aspx?t1=4&day=2025/3/10