软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2024/4/17）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2024/4/17

点击查看：更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容（2024/4/17）

阅读下列说明和C代码，回答问题1和问题2，将解答填入答题纸的对应栏内。
【说明】
某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表P，其中中Pi（i＝1，2，...，m）表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。
求解此切割方案的算法基本思想如下：
假设长钢条的长度为n英寸，最佳切割方案的最左边切割段长度为i英寸，则继续求解剩余长度为n－i英寸钢条的最佳切割方案。考虑所有可能的i，得到的最大收益rn对应的切割方案即为最佳切割方案。rn的递归定义如下：
rn=max1≤i≤n(pi+rn-i)对此递归式，给出自顶向下和自底向上两种实现方式
【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.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2024/4/17

信管网考友试题答案分享：

信管网cnitpm653985562261：
＜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】 动态规划，o（nlogn），o（n^2）＜/span＞＜/div＞递归是指数级，不可能比自底向上还快，所以不是nlogn 而是 2的n次方

信管网cnitpm630501712623：
【问题1】 1. i ＜= n 2.l ＜= j 3. p[l] + temp 4. p[j] ＝ temp 【问题2】 动态规划，o（nlogn），o（n^2）

信管网cnitpm630501712623：
【问题1】 1. i ＜= n 2.l ＜= j 3. p[l] + temp 4. p[j] ＝ temp 【问题2】 动态规划，o（nlogn），o（n^2） 【问题3】

信管网cnitpm633797129230：
i＜=n i＜=j temp＞=r[i]+r[j-i]?temp:r[i]+r[j-i]； r[j]=temp＞p[j]?temp:p[j] 动态规划 2^n n^2

信管网cnitpm630501712623：
【问题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.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2024/4/17