首页
登录
从业资格
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的
最全题库
2022-08-02
44
问题
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为( );对应的时间复杂度为( )。
假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装(请作答此空)个消防栓。以下关于该求解算法的叙述中,正确的是( )。A.4B.5C.6D.7
选项
A.4
B.5
C.6
D.7
答案
B
解析
快速排序由C.A.R.Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序采用的思想是分治思想。贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。整个算法的时间复杂度是O(nlogn)。场地上可以安排活动1、8、11为一个场地;活动2、6、9一个场地;活动3为一个场地;活动4、7为一个场地;活动5、10为一个场地,共5个场地。
转载请注明原文地址:https://tihaiku.com/congyezige/2425200.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
正常成人颅内压的范围是A.20~30mmHO B.50~100mmHO C.
以下关于内脏性疼痛的描述不正确的是A.痛觉敏感 B.范围不明显 C.定位不准
暴露疗法护理中最重要的是A.采用吸水性强的敷料包扎,达到要求的厚度和范围B.抬高
包扎疗法护理措施中不正确的是A.采用吸水性强的敷料包扎,达到要求的厚度和范围B.
正常成人颅内压的范围是A.20~30mmHO B.50~100mmHO C.
按控制的业务范围不同,控制可以分为A.技术控制、质量控制、资金控制、人力资源控制
颅内压的正常范围是A:0.4~0.6kPa(40~60mmH2O) B:0.7
若分页系统的地址结构如下图所示。 该系统页的大小为()字节,页号的取值范围
若采用16位补码表示整数,则可表示的整数范围为()。A.[-215,215]
数字话音的采样频率定义为8kHz,这是因为()。A.话音信号定义的频率范围最
随机试题
Nowadays,somethinghasgoneterriblywrongwithouronce-proudAmericanwa
Sleepispartofaperson’sdailyactivitycycle.Thereareseveraldifferentst
SomerecenthistorianshavearguedthatlifeintheBritishcoloniesinAmeri
[originaltext]M:Thenineteentwentieswereatimeofeconomicprogressformos
共用题干 龚建柱是某中学教师,30岁,每月税后收入4000元,年终奖金1000
A. B. C. D.
某社区目前正在进行为期两周的家庭日活动,社区中的社会工作者通过邀请专家开办讲座、
既能安胎,又能凉血的药物是 A.菟丝子 B.苎麻根 C.桑寄生 D.紫苏
外国投资者以股权并购境内公司所涉及的境内外公司的股权,应符合境外公司的股权最近1
处方调剂时药师审核的主要内容是A.必须做皮试的药物,是否注明实验及结果 B.剂
最新回复
(
0
)