阅读下列说明和C代码，回答问题1和问题2，将解答填入答题纸的对应栏内。

【说明】

某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表P，其中中P_i(i=1，2，...，m)表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。

求解此切割方案的算法基本思想如下：

假设长钢条的长度为n英寸，最佳切割方案的最左边切割段长度为i英寸，则继续求解剩余长度为n-i英寸钢条的最佳切割方案。考虑所有可能的i，得到的最大收益rn对应的切割方案即为最佳切割方案。rn的递归定义如下：

r_n=max_1≤i≤n(p_i+r_n-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表示)。

信管网参考答案：

【问题1】

(1)：i<=n

(2)：i<=j

(3)：temp=(temp>=r[i]+r[j-i])?temp:(r[i]+r[j-i])

(4)：r[j]=(temp>p[j])?temp:p[j];

【问题2】

(5)动态规划法

(6)O(2ⁿ)

(7)O(n²)

查看解析：www.cnitpm.com/st/396349820.html

相关推荐：

点击查看/下载：软件设计师历年真题汇总

点击查看：软件设计师在线培训课程 丨 免费试听课程

免费练习：软件设计师考试题库(模拟试题、章节练习、每日一练)