2. 从业资格
  3. 某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整

某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整

免费题库2022-08-02  69
问题 某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表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+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表示）。
选项
答案
解析 【问题1】
（1）：i＜=n
（2）：i＜=j
（3）：(temp>=p+r[j-i])?temp:(p+r[j-i])
（4）：r[j]=temp
或
（3）：(temp>=r+r[j-i])?temp:(r+r[j-i])
（4）：r[j]=(temp>p[j])?temp:p[j];
【问题2】
（5）动态规划法
（6）O(2n)
（7）O(n2)
【问题1】
在自顶向下实现过程中，n-i表示规模从大到小即n-1~0，即对应i的初始值为1，结束值为n，第一空填写i＜=n，递归式也有范围提示可以参照。
在自底向上实现过程中，采用双重嵌套循环，内层循环从1~j，第二空填写i＜=j。
第三空和第四空比较复杂，是具体的实现过程，是本题的难点。
根据题干内容，本题考查的是钢条切割问题最优化问题，求解的思路即先考虑最左侧的切割考虑，再依次向右扩展，中间的最优解结果记录在数组r[]中，并用temp中间变量传递最大值。
根据递归式rn=max1≤i≤n(pi+rn-i)，即r[]最终结果是该过程的最大值，（3）空给temp赋值，那么（4）空应该是将这个中间值传给最终的rn，也就是代码中的r[j]，即第四空填写r[j]=temp，那么此时第三空对应最大值的求取，也就是本算法的核心，这里的最大值是在1~j的规模范围循环比较，用temp放置本轮结果，再与下一轮结果进行比较，第三空temp=(temp>=p+r[j-i])?(temp:(p+r[j-i])。
【问题2】
题干中提到说考虑所有可能的i，得到最大收益的方式，而自底向上算法实现时，使用到数组把其中最优的解记录，并用r[]记录中间解，因此本题算法策略是动态规划法。
动态规划法自顶向下时需要对规模n进行求取，此时需要递归至规模1并最终返回结果规模n的解并记录，规模n-1同样如此，时间复杂度较大，可以达到O(2n)；
动态规划法自底向上时先求取规模1的解并记录，然后查询规模1的解从而求解规模2的解，以此类推，直至求取至规模n，有查询和循环求解2层嵌套循环，时间复杂度为O(n2)。
转载请注明原文地址:https://tihaiku.com/congyezige/2410694.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)