软题库 移动APP 扫码下载APP 随时随地移动学习 培训课程
当前位置:信管网 >> 在线考试中心 >> 信息系统项目管理师题库 >> 试题查看
试卷年份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表示)。


相关试题

推荐文章