阅读下列说明和 C 代码，回答问题 1 和问题 2，将解答填入答题纸对应栏内。 【说明】 某公司购买长钢条，将其切割后进行出售。切割钢条成本可以忽略不计，钢条长度为整英寸。已知价格表 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[]，int n)｛/*自顶向下*/ int r=0; int i; if(n==0){ retum 0; } for(i=1;（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;(2);i++){ temp=(3); } （4） } return r[n]; } 【问题 1】 根据说明，填充 C 代码中空（1）～（4）。 【问题 2】根据说明和 C 代码，算法采用设计策略为（5）。 求解 rn时，自顶向下方法时间复杂度为（6）；自底向上方法时间复杂度为（7）（用O 表示）。
正确答案及解析
正确答案
解析
你可能感兴趣的试题
在一条笔直公路一边有许多房子，现要安装消防栓，每个消防栓覆盖范围远大于房子面积，如下图所示。现求解能覆盖所有房子最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上点）。该问题求解算法基本思路为：从左端第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖所有房子。在剩余房子中重复上述操作，直到所有房子被覆盖。算法采用设计策略为（ ）；对应时间复杂度为（ ）。
假设公路起点A坐标为0，消防栓覆盖范围（半径）为20米，10栋房子坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法叙述中，正确是（请作答此空）。
-
- A.肯定可以求得问题一个最优解
- B.可以求得问题所有最优解
- C.对有些实例，可能得不到最优解
- D.只能得到近似最优解
- 查看答案
在一条笔直公路一边有许多房子，现要安装消防栓，每个消防栓覆盖范围远大于房子面积，如下图所示。现求解能覆盖所有房子最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上点）。该问题求解算法基本思路为：从左端第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖所有房子。在剩余房子中重复上述操作，直到所有房子被覆盖。算法采用设计策略为（ ）；对应时间复杂度为（ ）。
假设公路起点A坐标为0，消防栓覆盖范围（半径）为20米，10栋房子坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（请作答此空）个消防栓。以下关于该求解算法叙述中，正确是（ ）。
-
- A.4
- B.5
- C.6
- D.7
- 查看答案
在一条笔直公路一边有许多房子，现要安装消防栓，每个消防栓覆盖范围远大于房子面积，如下图所示。现求解能覆盖所有房子最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上点）。该问题求解算法基本思路为：从左端第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖所有房子。在剩余房子中重复上述操作，直到所有房子被覆盖。算法采用设计策略为（ ）；对应时间复杂度为（请作答此空）。
假设公路起点A坐标为0，消防栓覆盖范围（半径）为20米，10栋房子坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法叙述中，正确是（ ）。
-
- A.见图A
- B.见图B
- C.见图C
- D.见图D
- 查看答案
在一条笔直公路一边有许多房子，现要安装消防栓，每个消防栓覆盖范围远大于房子面积，如下图所示。现求解能覆盖所有房子最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上点）。该问题求解算法基本思路为：从左端第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖所有房子。在剩余房子中重复上述操作，直到所有房子被覆盖。算法采用设计策略为（请作答此空）；对应时间复杂度为（ ）。
假设公路起点A坐标为0，消防栓覆盖范围（半径）为20米，10栋房子坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法叙述中，正确是（ ）。
-
- A.分治
- B.动态规划
- C.贪心
- D.回溯
- 查看答案
阅读以下说明和流程图，填补流程图中空缺。 【说明】 设有整数数组A[1：N]（N小于1），其元素有正有负。下面流程图在该数组中寻找连续排列若干个元素，使其和达到最大值，并输出其起始下标K、元素个数L以及最大和值M。 例如，若数组元素依次为3，-6，2，4，-2，3，-1，则输出K=3，L=4,M=7。该流程图中考察了A[1：N]中所有从下标i到下标j（j≥i）各元素之和S，并动态地记录其最大值M。【流程图】
注：循环开始框内应给出循环控制变量初值和终值，默认递增值为1，格式为：循环控制变量=初值，终值
- 查看答案