答案及解析：[问答题]某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表p，其中pi（i＝1，2，…，m）表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。求解此

问题：

[问答题] 某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表p，其中pi（i＝1，2，…，m）表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。求解此切割方案的算法基本思想如下：假设长钢条的长度为n英寸，最佳切割方案的最左边切割段长度为i英寸，则继续求解剩余长度为n－i英寸钢条的最佳切割方案。考虑所有可能的i，得到的最大收益rn对应的切割方案即为最佳切割方案。rn的递归定义如下：rn=max1≤i≤n(pi+rn-i)对此递归式，给出自顶向下和自底向上两种实现方式。【C代码】/*常量和变量说明n：长钢条的长度p[]：价格数组*/#define LEN 100int Top_Down_Cut_Rod(int p[],int n){/*自顶向下*/int r=0;int i;if(n==0){return 0;}for(i=1;（1）;i++){int tmp=p[i]+Top_Down_Cut_Rod(p,n-i);r=(r>=tmp）r：tmp;}return r;}int Bottom_Up_Cut_Rod(int p[],int n){/*自底向上*/int r[LEN]={0};int temp=0;int i,j;for(j=1;j＜=n;j++){temp=0;for(i=1;（2）;i++){temp=（3）;}（4）;}return r[n];}【问题1】（8分）根据说明，填充C代码中的空（1）～（4）。【问题2】（7分）根据说明和C代码，算法采用的设计策略为（5）。求解rn时，自顶向下方法的时间复杂度为（6）；自底向上方法的时间复杂度为（7）（用O表示）。

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题