首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和图,填补流程图中的空缺。 【说明】 在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
阅读以下说明和图,填补流程图中的空缺。 【说明】 在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
admin
2008-08-01
117
问题
阅读以下说明和图,填补流程图中的空缺。
【说明】
在一条农村公路的一边稀疏地分布着房子,其分布如图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
软件设计师下午应用技术考试
软考中级
相关试题推荐
Web应用链接测试不包括(45)。
(12)是指把数据以及操作数据的相关方法组合在同一个单元中,使我们可以把类作为软件中的基本复用单元,提高其内聚度,降低其耦合度。面向对象中的(13)机制是对现实世界中遗传现象的模拟,通过该机制,基类的属性和方法被遗传给派生类。
针对逻辑覆盖(53)叙述是不正确的。
(46)叙述是正确的。①测试用例应由测试设计人员来制定。②测试点应由测试人员确立。③测试工作展开于项目立项后,而不是代码开发完成之后。④测试对象是源代码。
Web应用系统负载压力测试中,(60)不是衡量业务执行效率的指标。
针对电子政务类应用系统的功能测试,为设计有效的测试用例,应(34)。
为验证某呼叫中心是否能够承受大量呼叫信息同时呼入并得到正确处理,测试工程师一般采用______测试工具。A.负载压力B.代码C.网络仿真D.故障诊断
已知函数f()、g()的定义如下所示,执行表达式“x=f(5)”的运算时,若函数调用g(a)是引用调用(callbyreference)方式,则执行“x:f(5)”后x的值为(7);若函数调用g(a)是值调用(callbyvalue)方式,
软件测试的基本方法包括白盒测试和黑盒测试方法,以下关于二者之间关联的叙述,错误的是(61)。
若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n),且是稳定的(即如果待排序的序列中两个数据元素具有相同的值,在排序前后它们的相对位置不变),则可选择的排序方法是______。
随机试题
被誉为“千古词帝”的是________。
30岁,女性。脱发,光敏,面部蝶形红斑,关节痛,伴全身重度水肿,血红蛋白70g/L,抗核抗体1:640,血浆白蛋白14g/L尿蛋白(++++),血压11.7/8kPa(90/60mmHg)。首选治疗应是
脓血症( )。败血症( )。
女性,26岁,已婚。一周前因生气而出现心情不佳,四肢发麻,抽动、双下肢瘫痪,但无神经系统损害的体征,该患者可能的诊断是
2014年度,甲企业实现销售收入3000万元,当年发生广告费400万元,上年度结转未扣除广告费60万元。已知广告费不超过当年销售收入15%的部分,准予扣除。甲企业在计算2014年度企业所得税应纳税所得额时,准予扣除的广告费金额为()万元。
从众行为的原因有()。
以下哪些处罚种类属于教育行政处罚?()
计算机对主存的要求是速度快、容量大、价格低,但现实情况三者很难统一于一身,很难找到这种存储器件。为了能解决这一需求,在主存与CPU之间增加一级 cache,其主要目的是为解决(1),每次CPU访问主存时,都先要查询该单元数据是否已调入cache。为了把主存
单击命令按钮时,下列程序的执行结果为()。PrivateFunctionP(NAsInteger)StaticsumForI=1ToNsum=sum+INextIP=samEndFunctionPrivateS
Acollegelibraryisaninexhaustibleandeverchangingstorehouseofinformation.Newbooks,periodicals,andother【67】ofinfor
最新回复
(
0
)