问答题
.阅读下列说明和C代码,回答下列问题。
【说明】
某公司购买长钢条,将其切割后进行出售。切割钢条的成本可以忽略不计,钢条的长度为整英寸。己知价格表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 100
int Top_Down_Cut_Rod(int P[],intn){/*自顶向下*/
int r=0;
int i;
if(n==0){
return 0;
}
for(i=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;______;i++){
temp=______;
}
______;
}
return r[n];
}
问答题
1. 【问题1】
根据说明,填充C代码中的四个空。
【正确答案】i<=n
i<=i
temp=(temp>=r[i]+r[j-i]) ?temp:(r[i]+r[j-i])
r[j]=temp
【答案解析】
问答题
2. 【问题2】
根据说明和C代码,算法采用的设计策略为______。
求解rn时,自顶向下方法的时间复杂度为______:自底向上方法的时间复杂度为______(用O表示)。
【正确答案】动态规划
O(2n)
O(n2)
【答案解析】