信管网试题内容
信管网 导航

试卷名称:2018年上半年软件设计师考试下午真题试题(案例分析)

考试年份:2018年上半年

试题来源:《2018年上半年软件设计师考试下午真题试题(案例分析)》在线考试

试题内容

阅读下列说明和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表示)。
参考答案:暂时没有答案(仅供参考) 收藏

【解析】

普通会员无法查看试题解析。[开通试题解析服务]