在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧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),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法的叙述中,正确的是( )
![](https://assets.51tk.com/images/c84fa5136835e273_img/f2c66375b8280f7e.png)
假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法的叙述中,正确的是( )
A.分治
B.动态规划
C.贪心
D.回溯
B.动态规划
C.贪心
D.回溯
参考解析
解析:快速排序由C.A.R.Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序采用的思想是分治思想。贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。整个算法的时间复杂度是O(nlogn)。场地上可以安排活动1、8、11为一个场地;活动2、6、9一个场地;活动3为一个场地;活动4、7为一个场地;活动5、10为一个场地,共5个场地。
相关考题:
村里的房子都不是木房子,有些房子涂上了颜色。由此可以推断( )A.有些房子是涂了颜色的木房子B.有些房子不是涂了颜色的木房子C.有些房子或者是木房子或者是涂了颜色D.有些房子或者不是木房子或者没有涂颜色
甲有一所归自己所有的房子,甲的下列行为中,体现其物权性质的是()。 A、乙欲侵占该房子,甲制止乙侵占的行为B、甲自己居住该房子的行为C、甲拆除自己房子的行为D、甲出卖该房子请求他人支付价款的行为
甲有一所归自己所有的房子,甲的下列行为中,体现其物权性质的有( )。A.乙欲侵占该房子,甲制止乙侵占的行为B.甲自己居住该房子的行为C.甲拆除自己房子的行为D.甲出卖该房子请求他人支付价款的行为E.甲出租该房子请求他人支付租金的行为
阅读以下说明和图,填补流程图中的空缺。【说明】在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化问题,假设所有房子在同一直线上,并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。实现贪心算法的流程如图10-6所示,请填充其中空白并计算该算法的时间复杂度,其中:1.d[i](1≤i≤N)表示第i个房子到公路A端的距离,N表示房子的总数,房子的编号按照房子到公路A端的距离从小到大进行编号。2.s[k]表示第k(k≥1)个基站到公路A端的距离,算法结束后k的值为基站的总数。该算法的时间复杂度为(5)。
下列每题给出的四个选项中,只有一个选项符合题目要求。基于以下题干:在一不发达的街道上,一开发商要在该街道的一边同时建四幢编号为1,3,5和7的房子,在街道的对边建四幢编号为2,4,6和8的房子。编号为2,4,6和8的房子将分别与编号为1,3,5和 7的房子相对。每幢房子的风格恰好是R,S和T中的某一种,且满足以下条件:相邻的房子具有不同的风格:(1)两个S风格的房子不能对面;(2)每一个R风格的房子至少都有一个T风格的房子与其相邻;(3)3号房子是R风格的;(4)6号房子是S风格的。下面除了哪一幢房子之外都可能是T风格的房子?A.1B.2C.4D.7
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为( );对应的时间复杂度为( )。假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装(请作答此空)个消防栓。以下关于该求解算法的叙述中,正确的是( )。A.4B.5C.6D.7
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为( );对应的时间复杂度为(请作答此空)。假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法的叙述中,正确的是( )。A.O(lgn)B.O(n)C.(nlgn)D.O(n2)
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为( );对应的时间复杂度为( )。假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法的叙述中,正确的是(请作答此空)。A.肯定可以求得问题的一个最优解B.可以求得问题的所有最优解C.对有些实例,可能得不到最优解D.只能得到近似最优解
甲有一所归自己所有的房屋,甲的下列行为中,体现其物权性质的有( )A.乙欲侵占该房子,甲制止乙的侵占行为B.甲自己居住该房子的行为C.甲拆除自己房子的行为D.甲出卖该房子请求他人支付价款的行为E.甲对房子的装修行为
甲有一所归自己所有的房子,甲的下列行为中,体现其物权性质的有:()A、乙欲侵占该房子,甲制止乙侵占的行为B、甲自己居住该房子的行为C、甲拆除自己房子的行为D、甲出卖该房子请求他人支付价款的行为
单选题国王要为自己的女儿挑选一个最聪明勇敢的女婿,他向所有的求婚者宣称他已经把公主和两只狮子分别关进了三间房子,然后在三间房子的门上分别写了一句话,让求婚者们去打开自己认为可以打开的门。第一间房门上写着:“这间房子里有狮子。”第二间房门上写着:“公主在第一间房子里。”第三间房门上写着:“这间房子里有狮子。”其实这三句话中,只有一句话是真的。据此可以推断( )。A公主在第一间房子里B公主在第二间房子里C公主在第三间房子里D三间房子里关的都是狮子
多选题甲有一所归自己所有的房子,甲的下列行为中,体现其物权性质的有:()A乙欲侵占该房子,甲制止乙侵占的行为B甲自己居住该房子的行为C甲拆除自己房子的行为D甲出卖该房子请求他人支付价款的行为
单选题甲男与乙女结婚后,共同购买了一辆汽车和一套房子。关于甲和乙对汽车和房子的所有权,下列说法正确的是________。A对汽车和房子都是共同所有B对汽车和房子都是按份所有C对汽车是共同所有,对房子是按价所有D对汽车是按份所有,对房子是共同所有
单选题国王要为自己的女儿挑选一个最聪明勇敢的女婿,他向所有的求婚者宣称他已经把公主和两只狮子分别关进了三间房子,然后在三间房子门上分别写了一句话,让求婚者们去打开自己认为可以打开的门。第一间房上写着:“这间房子里有狮子。”第二间房门上写着:“公主在第一间房子里。”第三间房门上写着:“这间房子里有狮子。”其实这三句话中,只有一句话是真的。据此可以推断( )。A公主在第一间房子里B公主在第二间房子里C公主在第三间房子里D三间房子里关的都是狮子