首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和图,填补流程图中的空缺。 【说明】 在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
阅读以下说明和图,填补流程图中的空缺。 【说明】 在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
admin
2008-08-01
122
问题
阅读以下说明和图,填补流程图中的空缺。
【说明】
在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化问题,假设所有房子在同一直线上,并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。
实现贪心算法的流程如图10-6所示,请填充其中空白并计算该算法的时间复杂度,其中:
1.d
(1≤i≤N)表示第i个房子到公路A端的距离,N表示房子的总数,房子的编号按照房子到公路A端的距离从小到大进行编号。
2.s[k]表示第k(k≥1)个基站到公路A端的距离,算法结束后k的值为基站的总数。
该算法的时间复杂度为(5)。
选项
答案
(1)k=0 (2)j<=N,或其等价形式 (3)k=k+1,或其等价形式 (4)d[i]+6,或其等价形式 (5)O(N),或O(n)
解析
该问题可以建模为如图10-7所示,其中直线表示房子所在的直线,实心正方形表示房子。问题是要求如何在该直线上布局机站,使其能覆盖所有的房子,并且所用机站的数量要尽可能的少。这是一个通过进行一系列选择求最优解的问题。
分析该问题,发现其具有最优子结构,并且具有贪心选择性质,故该问题可以用贪心算法来求解。算法思想:问题的规模为N。从第一个房子(最左端)开始布局机站,把第一个机站放置在该房子右方的6公里处,这时该机站会覆盖从第一个房子到其右方 12公里的直线的长度上的所有房子,假设覆盖了N1个房子。此时问题规模变成了N-N1。把第一个机站覆盖的房子去掉,再从N-N1中选择第一个(最左端)房子开始布局机站,将第二个机站放置在该房子右方的6公里处。依此布局,直到覆盖所有的房子。
图10-8是问题解的模型,其中直线表示房子所在的直线,实心正方形表示房子,实心圆形表示机站,虚线圆以对应机站为圆心,直径为机站的覆盖范围,即对应机站的覆盖范围。
算法中包含两个循环,但实际上只是遍历所有房子一次,故算法复杂度是O(N)。
转载请注明原文地址:https://kaotiyun.com/show/pfDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
典型的软件测试过程模型有(46)等,在这些模型中,(47)强调了测试计划等工作的先行和对系统需求和系统设计的测试,(48)对软件测试流程予以了说明。
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
以下(53)属于在GB/T18905《评价者用的过程》中定义软件评价过程的特性。①可重复性②可再现性③公正性④客观性⑤合理性
从数据库管理系统的角度看,数据库系统一般采用如下图所示的三级模式结构。图中①②处应填写(26),③处应填写(27)。
关于数据库索引,以下表述正确的是(57)。①如果对表创建了索引,那么更新、插入和删除表中的记录都将导致额外的系统开销。②全表扫描一定比使用索引的执行效率低。③在字段选择性很低的情况下适用索引。④一个表创建的索引越多,对系统的性能提升越大。
黑盒测试中,(59)是根据输出对输入的依赖关系设计测试用例。
软件测试原则中指出“完全测试是不可能的”,主要原因是______。A.输入量太大、输出结果太多以及路径组合太多B.自动化测试技术不够完善C.测试的时间和人员有限D.仅仅靠黑盒测试不能达到完全测试
下面关于软件测试模型的描述中,不正确的包括______。①V模型的软件测试策略既包括低层测试又包括高层测试,高层测试是为了源代码的正确性,低层测试是为了使整个系统满足用户的需求②V模型存在一定的局限性,它仅仅把测试过程作为在需求分析、概要设
在C程序中,若表达式中的算术运算对象的类型不同,则需要先统一为相同类型后再进行计算。例如,表达式“a-b”中,若a是双精度浮点型变量,b是整型变量,为了尽可能保证运算精度,通常进行的处理是______。
完成下列命令行,对网络接口进行地址初始化配置。firewall(config)#ipaddressinside(1)(2)firewall(config)#ipaddressoutside(3)(4)管道命令的作用是允许数据流从
随机试题
“老仲马是大仲马的父亲,大仲马是小仲马的父亲,所以老仲马不是小仲马的父亲。”这一关系推理属于()
脂质体由磷脂和附加剂组成,常用的可以调节双分子层流动性、通透性的附加剂为
有关高温作业人员的矿物质和微量元素供给的叙述,不正确的是()。
A、心脾热盛B、气血两虚C、热盛伤津,阴精亏损D、脾虚而寒湿壅盛E、热邪亢盛舌质红绛而有裂纹。属于()
一、背景某机电安装施工单位承建某城市的一项大型图书馆机电安装工程。合同造价2400万元,其中主材料费和设备费占65%,工期为8个月。合同约定:(1)工程用主材料和设备由甲方供货,其价款在当月发生的工程款中抵扣。(2)
下列关于资产负债表中“应收账款”项目填列依据的表述中,正确的有()。
影响行业风险产生的因素有()。
市政道路及管线设计软件,属于计算机
A.exploreB.distinctC.artisticD.inaccessibleE.subjectiveF.highlyG.factualH.declineI.definitivelyJ.currents
WhatIfACollegeEducationJustIsn’tforEveryone?LongbeforethepresidentsworelastyearthatAmericawill"havetheh
最新回复
(
0
)