首页
登录
从业资格
某公司购买长钢条,将其切割后进行出售。切割钢条的成本可以忽略不计,钢条的长度为整
某公司购买长钢条,将其切割后进行出售。切割钢条的成本可以忽略不计,钢条的长度为整
免费题库
2022-08-02
65
问题
某公司购买长钢条,将其切割后进行出售。切割钢条的成本可以忽略不计,钢条的长度为整英寸。已知价格表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
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
阅读以下说明,回答问题1至问题3,将答案填入答题纸的对应栏内。【说明】M公司为了
阅读下列说明,回答问题l至问题3,将解答填入答题纸的对应栏内。【说明】GD公司成
某公司要用一套新的订单管理系统替换旧的系统,为实现平稳转换,公司决定先上线新系统
某航空公司拟开发一个机票预订系统,旅客预订机票时使用信用卡付款。付款通过信用卡公
数据字典中“数据项”的内容包括:名称、编号、取值范围、长度和()A.处理频率
假设某公司业务的用例模型中,“检验”用例需要等到“生产”用例执行之后才能执行,这
在许多企业里,某个员工离开原公司后,仍然还能通过原来的账户访问企业内部信息和资源
()作为重要的IT系统管理流程,可以解决IT投资预算、IT成本、效益核算和投资
信息系统除了对企业管理效率的提高和成本的降低具有显著作用外,还有促进企业运作方式
成本核算的主要工作是定义成本要素。对IT部门而言,理想的方法应该是按照()定义
随机试题
Noonecanusecellphonesinanyareasatthehospitalwhereequipmentmightbe
Youshouldspendabout20minutesonQuestions1-13whicharebasedonReadingP
[originaltext]W:WhataretheadvantagesofE-education,ProfessorGu?M:There
Aswarspreadstomanycornersoftheglobe,childrensadlyhavebeendrawn
关于IPv6重复地址检测(DuplicateAddressDetection
历史教师在创设有效的历史教学情境时,应创设的教学情景有哪些?
《国际海运条例》适用于与国际海上运输相关的辅助性经营活动,包括( )、国际船舶
当基金投资于交易不活跃的证券时,资产估值问题则要复杂得多。()
我国金融债券的品种主要包括()。 A.中央银行票据B.政策性银行金融债券
一男孩,10岁。右膝部疼痛跛行2年,有夜间痛,检查右膝活动良好,右髋不能伸直,大
最新回复
(
0
)