2. 计算机
  3. 阅读下列说明和C代码，回答问题1和问题2，将解答填入答题纸的对应栏内。 【说明】 某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。 已知价格表P，其中Pi(i=1，2，…，m)表示长度为i英寸的

阅读下列说明和C代码，回答问题1和问题2，将解答填入答题纸的对应栏内。 【说明】 某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。 已知价格表P，其中Pi(i=1，2，…，m)表示长度为i英寸的

admin2019-10-08  36
问题 阅读下列说明和C代码，回答问题1和问题2，将解答填入答题纸的对应栏内。
    【说明】
    某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。
    已知价格表P，其中Pi(i=1，2，…，m)表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。
    求解此切割方案的算法基本思想如下：
    假设长钢条的长度为n英寸，最佳切割方案的最左边切割段长度为i英寸，则继续求解剩余长度为n-i英寸钢条的最佳切割方案。考虑所有可能的i，得到的最大收益rn对应的切割方案即为最佳切割方案。rn的递归定义如下：
    m=max1≤i≤n(pi+m-i)
    对此递归式，给出自顶向下和自底向上两种实现方式。
   【C代码】
  ／*常量和变量说明
  n：长钢条的长度
  P[]：价格数组
  *／
  #define LEN 100
  int Top_Down_Cut_Rod(int P[]，int n){／*自顶向下*／
    int r=0：
    int i；
    if(n==0) {
    return 0：
    }
    for(i=1；______(1)；i++)  {
    int trap=P+Top_Down_Cut_Rod(p，n-i)；
    r=(r＞-trap)?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]；
    }
根据说明和C代码，算法采用的设计策略为______(5)。求解rn时，自项向下方法的时间复杂度为______(6)；自底向上方法的时间复杂度为______(7)(用O表示)．
选项
答案(5)动态规划 (6)0(22) (7)O(n2)
解析
转载请注明原文地址:https://kaotiyun.com/show/GsxZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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