首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和图,填补流程图中的空缺。 【说明】 在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
阅读以下说明和图,填补流程图中的空缺。 【说明】 在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
admin
2008-08-01
100
问题
阅读以下说明和图,填补流程图中的空缺。
【说明】
在一条农村公路的一边稀疏地分布着房子,其分布如图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
软件设计师下午应用技术考试
软考中级
相关试题推荐
下述关于错误处理流程管理的原则,(49)的说法是不正确的。
阅读下列流程图:当用判定覆盖法进行测试时,至少需要设计(44)个测试用例。
负载压力性能测试需求分析时,应该选择(63)类型的业务作为测试案例。 ①高吞吐量的业务 ②业务逻辑复杂的业务 ③高商业风险的业务 ④高服务器负载的业务 ⑤批处理的业务
用等价类划分法设计8位长数字类型用户名登录操作的测试用例,应该分成(44)个等价区间。
假设A、B为布尔变量,对于逻辑表达式(A&&B||C),需要______个测试用例才能完成判定覆盖(DC)。A.2B.3C.4D.5
关系数据库管理系统应能实现的专门关系运算包括______。A.选择、索引、统计B.选择、投影、连接C.关联、更新、排序D.显示、打印、制表
模块A的功能为:从数据库中读出产品信息,修改后存回数据库,然后将修改记录写到维护文件中。该模块内聚类型为(38)内聚。以下关于该类内聚的叙述中,正确的是(39)。(39)
设系统中有R类资源m个,现有n个进程互斥使用。若每个进程对R资源的最大需求为w,那么当m、n、w取下表的值时,对于下表中的a~e五种情况,(26)两种情况可能会发生死锁。对于这两种情况,若将(27),则不会发生死锁。
以下关于数据流图的叙述中,不正确的是()。
将图2-1中(1)和(2)空缺名称填写在应的位置。在本质上,ADSL采用的什么多路复用方式?
随机试题
常用的剖视图有:_______、_______、_______和剖面图。
夏日高热无汗,宜用哪味中药煎汤熏洗躯体( )
一个估价项目完成后,应保存的档案资料包括()。
监理单位的产品是( )。
按照上海证券交易所配股规则,拥有某种股票配股权证的投资者,可委托买入不超过可配股数的股票,具体方式为向场内申报( )。
詹森是一名运动员,平时训练有素,实力雄厚,但在体育赛场上却连连失利,让自己和他人失望,不难看出这主要是压力过大,过度紧张所致。由此人们把这种平时表现良好,但由于缺乏应有的心理素质而导致正式比赛失败的现象称为詹森效应。下列各项,没有体现詹森效应的一项是(
多项式f(x)=x3+a2x2+ax-1被x+1除余-2,则实数a等于().
以下叙述中正确的是
掩码“LLL000”对应的正确输入数据是
Inlastweek’sTribune,therewasaninterestingletterfromMr.J.StewartCook,inwhichhesuggestedthatthebestwayofavo
最新回复
(
0
)