首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和图,填补流程图中的空缺。 【说明】 在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
阅读以下说明和图,填补流程图中的空缺。 【说明】 在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
admin
2008-08-01
121
问题
阅读以下说明和图,填补流程图中的空缺。
【说明】
在一条农村公路的一边稀疏地分布着房子,其分布如图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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
针对以下C语言程序段,对于(MaxNum,Type)的取值,至少需要(62)个测试用例能够满足判定覆盖的要求。while(MaxNum-->0){if(10==Type)x=y*2;elseif(100==Type)
在某大学学籍管理信息系统中,假设学生年龄的输入范围为16~40,则根据黑盒测试中的等价类划分技术,下面划分正确的是(46)。
在CPU与主存之间设置高速缓冲存储器(Cache)的目的是为了(2)。
不属于界面元素测试的是(50)。
黑盒测试中,(59)是根据输出对输入的依赖关系设计测试用例。
假设在程序控制流图中有14条边、10个节点,则控制流程图的环路复杂性V(G)等于______。A.12B.8C.6D.4
以下关于软件生命周期的叙述不正确的是______。A.软件生命周期包括以下几个阶段:项目规划、需求定义和需求分析、软件设计、程序编码、软件测试、运行维护B.程序编码阶段是将软件设计的结果转换成计算机可运行的程序代码。为了保证程序的可读性、易维护性和提高
M软件公司的软件产品注册商标为M,为确保公司在市场竞争中占据优势,对员工进行了保密约束。此情形下该公司不享有()。
对某商店业务处理系统采用数据流图(DFD)进行功能建模,其中“检查订货单”是其中的一个①。由于在进行订货单检查时,需要根据客户的欠款情况、订单金额等多个条件判断是否采取发出催款单、准备货物、发出发货单等行为,此时适合采用②进行描述。①处
随机试题
A.小肠化物,泌别清浊B.大肠传导,排出糟粕C.二者均是D.二者均非(2002年第101,102题)胃主通降,促进()
以下估计信度的方法中,多用在预测性测验上的是()
下列哪些可引起代谢性碱中毒
在流脑发病机制中起主要作用的物质是
镜下血尿是指
亚硝酸盐中毒的特效解毒药是
HIV是()
某旅行社导游李某带团游览一处地势险峻的景点时,众人争相拍照,李某未提示注意安全,该团游客崔某不慎将唐某撞下陡坡摔伤。下列哪些选项是正确的?()
与精心设计的人员招聘申请表相比,个人简历的特点是()。
对空气断路器或者液压传动的油断路器,当气压或液压低至不允许实行重合闸时,应将重合闸()。
最新回复
(
0
)