首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在一条笔直公路的一边有许多房子,现要安装消火栓,每个消火栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消火栓数和安装方案(问题求解过程中,可将房子和消火栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧
在一条笔直公路的一边有许多房子,现要安装消火栓,每个消火栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消火栓数和安装方案(问题求解过程中,可将房子和消火栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧
admin
2019-10-08
37
问题
在一条笔直公路的一边有许多房子,现要安装消火栓,每个消火栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消火栓数和安装方案(问题求解过程中,可将房子和消火栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消火栓,去掉被该消火栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为________(1);对应的时间复杂度为________(2)。
假设公路起点A的坐标为0,消火栓的覆盖范围(半径)为20m,10栋房子的坐标为(10,20,30,35,60,80,160,210,260,300),单位为m。根据上述算法,共需要安装________(3)个消火栓。以下关于该求解算法的叙述中,正确的是________(4)。
(4)
选项
A、肯定可以求得问题的一个最优解
B、可以求得问题的所有最优解
C、对有些实例,可能得不到最优解
D、只能得到近似最优解
答案
A
解析
对于第一个空,本题使用的是分治法。
1)分治法特征:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决;否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。
2)动态规划法:在求解问题中,对于每一步决策,列出各种可能的局部解,再依据某种判定条件,舍弃那些肯定不能得到最优解的局部解,在每一步都经过筛选,以每一步都是最优解来保证全局是最优解。本题情景没有列出所有的可能解进行筛选,因此,本题不属于动态规划法。
3)回溯法:回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当搜索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。本题情景没有探索和回退的过程,因此,本题不属于回溯法。
4)贪心法:总是做出在当前来说是最好的选择,而并不从整体上加以考虑,它所做的每步选择只是当前步骤的局部最优选择,但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解,因此其耗费时间少,一般可以快速得到满意的解,但得不到最优解。在本题情景中,没有给出每步选择的局部最优判断条件,因此,本题不属于贪心法。
舍弃已被覆盖的房子,可以将问题的规模逐步缩小,形成规模较小的子问题,而这些问题的求解与原问题的求解过程相同,因此本题属于分治法的算法思想。
由于本题的算法过程,是依次与各个房子进行判断,当所有房子都被比较之后,则问题结束,因此时间复杂度与房子的个数相关,本问题的时间复杂度应该趋于现象,为O(n)。
对于第三个空,关于对应序列(10,20,30,35,60,80,160,2lO,260,300):
第一轮放置:在第一座房子x=10的右侧20m处安装一个消火栓,可以覆盖10,20,30,35这4栋房子;
第二轮放置:去掉前4栋房子,在第5栋房子x=60的右侧20米处安装一个消火栓,可以覆盖60、80这2栋房子;
第三轮放置:去掉前面已覆盖的房子,在第7栋房子x=160的右侧20m处安装一个消火栓,只可以覆盖160这一栋房子:
第四轮放置:去掉前面己覆盖的房子,在第8栋房子x=210的右侧20m处安装一个消火栓,可以覆盖210这一栋房子
第五轮放置:去掉前面己覆盖的房子,在第9栋房子x=260的右侧20米处安装一个消火栓,可以覆盖260、300这2栋房子;
房子全部覆盖完毕,因此共需安装5个消火栓。
对于第四个空,对于得到一个最优解是动态规划的特点,可以得到问题所有的最优解,是回溯法的特征,可以排除A、B选项。对于C、D选项,C的语法更为合理一些。
转载请注明原文地址:https://jikaoti.com/ti/zyG7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明和流程图,回答问题1至问题3。【说明】某城市电信局受理了许多用户申请在指定电话上开设长话业务。长话包括国内长途和国际长途。电信局保存了长话用户档案和长话业务档案。
指出算法的流程图中(1)~(3)处的内容。指出测试用例设计中(4)~(9)处的内容。
阅读下列程序说明和C程序,将应填入程序中(n)处的字句,写在对应栏内。【程序说明】本程序先从文件读人各考生的准考证号(设为整型数)及成绩,并将其存放在一棵检索二叉树上,二叉树结点的健值是成绩,每个结点带一链表,链表结点存放取得该成绩的考生
阅读以下说明和数据流图,回答问题1~3问题。[说明]干部信息管理系统(CMIS)是用于对干部信息进行管理的特定系统。利用该系统,干部科可以对本单位干部信息进行管理,根据不同命令对信息进行增、删、改、内部调动,打印人事表格,进行统计、检索。干
阅读以下说明,回答问题1和问题2,将解答写在对应栏内。【说明】一个野生动物园,有如下动物:老虎、豹、狼、丹顶鹤、鹦鹉、天鹅、金鱼、热带鱼、鳄鱼等等。
阅读以下说明和C++码,将应填入(n)处的字名写在对应栏内。从下列的3道试题(试题五至试题七)中任选1道解答。如果解答的试题数超过1道,则题号小的1道解答有效。[说明]编写程序,把从键盘上输入的一批整数(以-1作为终止输入的标志)保存
如果将上述应用的数据库设计成如下关系模式;RS(A#,A1,A2,A3,B#,B1,B2,D1),请指出该关系模式的候选键。如果将上述应用的数据库设计为如下三个关系模式:R1(A#,A1,A2,A3)R2(B#,B1,B2)
阅读下列C++程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】本程序将两个从小到大的有序链表合成一个新的从小到大的有序链表。链表的每一项由类Node描述,而链表由类List描述。类List的成员函数有以下几个。①createList
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,
随机试题
患者,男,40岁。因“发热、鼻塞10天,咳嗽伴咯血3天”入院,伴关节痛、肌肉痛及视力下降。查体:双下肺呼吸音减弱。胸腔积液为渗出液,小便常规示:血尿(+++),蛋白尿(++),可见细胞管型。B超示:双侧胸腔少量积液。目前诊断首先考虑
连续抽油杆可以大幅度降低抽油杆的失效频率,一般可降低()。
与心肌损伤标志物肌钙蛋白T相比,肌钙蛋白Ⅰ的优点是
A.谷风B.陆风C.城市热岛D.山风E.海风夜晚,山坡表面散热量大,冷却快,气温低于谷地,冷空气下沉,形成()
A.2~3日B.3~4日C.5~7日D.3~5日E.14日阑尾穿孔切除术后几日常可发生腹腔脓肿
下列期货公司人员中,需要具备期货从业人员资格的有( )。
在一定程度上无法通过一定范围内的分散化投资来降低的风险是()。
质权合同的条款包括()。
下面关于ARM嵌入式处理器的GPIO的叙述中,错误的是()。
A、Differencesandsimilaritiesbetweentwocultures.B、Americanculture.C、Japaneseculture.D、Theintegrationoftwocultures.
最新回复
(
0
)