首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和图,填补流程图中的空缺。 【说明】 在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
阅读以下说明和图,填补流程图中的空缺。 【说明】 在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
admin
2008-08-01
89
问题
阅读以下说明和图,填补流程图中的空缺。
【说明】
在一条农村公路的一边稀疏地分布着房子,其分布如图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
软件设计师下午应用技术考试
软考中级
相关试题推荐
高速缓存cache与主存间采用全相联地址映像方式,高速缓存的容量为4MB,分为4块,每块1MB,主存容量为256MB。若主存读写时间为30ns,高速缓存的读写时间为3ns,平均读写时间为3.27ns,则该高速缓存的命中率为(3)%。若地址变换表如下所示,
设关系模式R(A,B,C),传递依赖指的是(16);下列结论错误的是(17)。
黑盒测试中,(59)是根据输出对输入的依赖关系设计测试用例。
一个软件系统的生存周期包含可行性分析和项目开发计划、需求分析、设计(概要设计和详细设计)、编码、测试和维护等活动,其中(18)是软件工程的技术核心,其任务是确定如何实现软件系统。
V模型描述了软件基本的开发过程和测试行为,描述了不同测试阶段与开发过程各阶段的对应关系。其中,集成测试阶段对应的开发阶段是______。A.需求分析阶段B.概要设计阶段C.详细设计阶段D.编码阶段
若有关系R(A,B,C,D,E)和S(B,C,F,G),则R与S自然联结运算后的属性列有(17)个,与表达式π1,3,6,7(σ3<6(RS))等价的SQL语句如下:SELECT(18)FROM(19)WHERE(20); (1
某教学管理数据库中,学生、课程关系模式和主键分别为:S(学号,姓名,性别,家庭住址,电话),关系S的主键为学号;C(课程号,课程名,学分),关系C的主键为课程号。假设一个学生可以选择多门课程,一门课程可以由多个学生选择。一旦学生选择某门课程必定有该课程的成
软件测试的基本方法包括白盒测试和黑盒测试方法,以下关于二者之间关联的叙述,错误的是(61)。
设数组a[1..10,1..8]中的元素按行存放,每个元素占用4个存储单元,已知第一个数组元素a[1,1]的地址为1004,那么a[5,6]的地址为________________。
随机试题
文职人员1年内不得晋升岗位等级的等次为()。
体现有利原则的是体现公正原则的是
A.变质性炎症B.浆液性炎症C.增生性炎症D.化脓性炎症E.出血性炎症流行性脑脊髓膜炎属于
刑法分则某条文规定:“犯A罪的,处3年以下有期徒刑,并处或者单处罚金”。被告人犯A罪,但情节较轻,且其身无分文。对此,下列哪一判决符合该条规定?()(2002年卷二第1题)
根据《建设工程安全生产管理条例》,施工单位应当自施工起重机械和整体提升脚手架、模板等自升式架设设施验收合格之日起()日内,向建设行政主管部门或者其他有关部门登记。登记标志应当置于或者附着于该设备的显著位置。
2015年7月1日,甲公司应收乙公司账款的账面余额为8万元,由于乙公司发生财务困难,无法偿付应付账款。经双方协商同意,采取将乙公司所欠债务转为乙公司股本的方式进行债务重组,假定乙公司普通股的面值为每股1元,乙公司以4万股普通股抵偿该项债务,股票每股市价为1
银行为什么要保有一定规模的资本?
ThreeEnglishdictionariespublishedrecentlyalllayclaimtopossessinga"new"feature.TheBBCEnglishDictionary,contains
Thispassagemightbetakenfrom______.Whichdoyouthinkwouldbethebesttitleforthepassage?
夜间大学
最新回复
(
0
)