软件设计师案例分析当天每日一练试题地址:www.cnitpm.com/exam/ExamDayAL.aspx?t1=4
往期软件设计师每日一练试题汇总:www.cnitpm.com/class/27/e4_1.html
软件设计师案例分析每日一练试题(2022/5/22)在线测试:www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2022/5/22
点击查看:更多软件设计师习题与指导
软件设计师案例分析每日一练试题内容(2022/5/22)
阅读下列说明和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/st/396349820.html
信管网考友试题答案分享:
信管网cnitpm509362975264:
问题1:
1;i<=n
2: i<=n
3:
4: r[n] = temp
问题2:
动态规划法
o(nlogn)
o(n2)
信管网suhx:
【问题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,
【问题2】:
算法设计策略为:分治
自顶向下时间复杂度为:o(n的平方)
自底向上时间复杂度为:o(n的三次方)
信管网试题答案与解析:
www.cnitpm.com/st/396349820.html