首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下技术说明和问题模型图,根据要求回答问题1和问题2。 【说明】 某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点AP(Access Poin)。假设每个无线AP覆盖范围的半径是6米,因此必须使得每台笔记本电脑上的无线网卡到某个无线A
阅读以下技术说明和问题模型图,根据要求回答问题1和问题2。 【说明】 某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点AP(Access Poin)。假设每个无线AP覆盖范围的半径是6米,因此必须使得每台笔记本电脑上的无线网卡到某个无线A
admin
2012-12-10
87
问题
阅读以下技术说明和问题模型图,根据要求回答问题1和问题2。
【说明】
某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点AP(Access Poin)。假设每个无线AP覆盖范围的半径是6米,因此必须使得每台笔记本电脑上的无线网卡到某个无线AP的直线距离不超过6米。为了简化问题,假设所有无线网卡在同一直线上,并且无线AP沿该直线放置。该问题可以建模为如图1-16所示,其中直线表示无线网卡所在的直线,实心正方形表示无线网卡。现利用贪心策略实现用尽可能少的无线AP覆盖所有的无线网卡。
实现贪心算法的流程如图1-17所示。其中,①d
(1≤i≤N)表示第i张无线网卡到通道A端的距离,N表示无线网卡的总数,无线网卡的编号按照无线网卡到通道A端的距离从小到大进行编号;②s[k]表示第k(k≥1)个无线AP到通道A端的距离。算法结束后k的值为无线AP的总数。
选项
答案
(1)k=0 (2)j<=N或其等价形式 (3)k=k+1或其等价形式 (4)d[i]+6或其等价形式
解析
本试题的题干说明中已将无线网卡分布问题建模(如图1-16所示)。其中,直线表示无线网卡所在的直线,实心正方形表示无线网卡。而要求解的问题是要求如何在该直线上布局无线AP,使其能覆盖所有的无线网卡,并且所用无线AP的数量要尽可能的少。这是一个通过进行一系列选择求最优解的问题。
分析该问题,发现其具有最优子结构,并且具有贪心选择性质,故该问题可以用贪心算法来求解。贪心算法思想是:问题的规模为N,从第1个无线网卡(最左端)开始布局无线AP,把第1个无线AP放置在该无线网卡右方的6m处,此时该无线AP会覆盖从第1个无线网卡到该无线网卡右方直线长度为12m的所有无线网卡,假设覆盖了N1个无线网卡。此时问题规模变成了N-N1,接着把第1个无线AP覆盖的无线网卡去掉,再从N-N1中选择第1个(最左端)无线网卡开始布局无线AP,将第2个无线AP放置在该无线网卡右方的6m处。依此布局,直到覆盖所布的无线网卡。
图1-20是问题解的模型。其中,直线表示无线网卡所在的直线,实心正方形表示无线网卡,实心圆形表示无线AP,虚线圆以对应无线AP为圆心,直径为无线AP的覆盖范围,即对应无线AP的覆盖范围(12米)。
实现贪心算法的流程见图1-17。由于“算法结束后k的值为无线AP的总数”,因此在算法开始处需要对变量k赋初值,即(1)空缺处所填写的内容是“k=0”。
该贪心算法中,N表示无线网卡的总数,且无线网卡的编号按照无线网卡到通道A端的距离从小到大进行编号,d
1≤i≤N)表示第i个无线网卡到通道A端的距离。当判断第i个无线网卡未超过无线网卡总数N,而求解下一个无线网卡(即第i+1个无线网卡,或第j个无线网卡)所归属的无线AP时,也需要判断第j个无线网卡是否超过无线网卡总数N,以及第j个无线网卡与第j个无线网卡之间的距离是否超过12米,因此(2)空缺处所在的判断条件是“j<=N&&d
-d
<=12”,即该空缺处所填写的内容是“j<=N”或其等价形式。
若第j个无线网卡未超过无线网卡总数N,且第j个无线网卡与第j个无线网卡之间的距离未超过12米,则可以求解再下一个无线网卡(即第i+2个无线网卡,或第j+1个无线网卡)所归属的无线AP。反之,则需要记录无线AP的总数k,即(3)空缺处所填写的内容是“k=k+1”或其等价形式;以及记录第A(A)1)个无线AP到通道A端的距离,即(4)空缺处所填写的内容是“d
+6”或其等价形式。
当求解完第k个无线AP(覆盖了N1个无线网卡)的布局后,需要把第A个无线AP覆盖的无线网卡去掉,再从N-N1中选择第1个(最左端)无线网卡开始布局第k+1个无线AP。依此不断求解,直到覆盖所有的无线网卡。
转载请注明原文地址:https://kaotiyun.com/show/TnjZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
数据的收集方式可有多种,分别适用于各种情况。以下数据收集方式,不恰当的是______。
在Word2010中,要对设定好纸张大小的文档进行每页行数和每行字数调整,可通过页面设置对话框中的()命令进行设置。
某企业长期从事大量的数据处理工作,所建立的一系列规范中一般不包括________。
在Excel2007中,若在单元格A1中输入函数“=MID(“RUANKAO”,1,4)”,按回车键后,则A1单元格中的值为()。
计算机每次启动时自动运行的计算机病毒称为______病毒。
在PowerPoint2007中,为精确控制幻灯片的放映时间,可使用______功能。
某Word文档共有100页,现需要打印该文档的第5页到第9页和第12页,在打印对话框中,可输入打印页码()。
某PPT文件共有8张幻灯片,现选中第6张幻灯片,对其设置新的背景颜色,单击“应用”按钮后,则()。
为什么一般处理“震荡波”病毒时,首先要把被侵入的计算机系统从网络上断开?在计算机系统发现病毒并清除以后,在未接入网络之前,从安全方面考虑,若需重新安装操作系统,通常需要执行以下几项主要工作后,方可接入网络。请给出下列工作的合理顺序。A.安装操作
防火墙包过滤规则的默认策略为拒绝,下表给出防火墙的包过滤规则配置界面。若要求内部所有主机能使用IE浏览器访问外部IP地址为202.117.118.23的Web服务器,为图中(1)~(4)空缺处选择正确答案。(1)A.允许B.拒绝(2)A.192
随机试题
已知D(X)=9,D(Y)=16,X与Y的相关系数为0.5,则D(X+2Y)=________.
课程标准
关于全心全意为人民健康服务,不正确的是
患者,女性,30岁,乳腺癌根治术后。护士在出院指导中,告知早期发现复发乳腺癌时最应强调的内容是
依次填入下列各句横线处的词语,恰当的一组是()。 (1)曹操四言诗的雄浑,陶渊明田园诗的恬淡,自然受人称誉;而张旭草书的奇伟飞动,颜真卿楷书的厚重雄伟,也同样令人________。 (2)在总统选举投票现场的门外,________着
()是会计专业技术职务。
证券投资顾问向客户提供投资建议的()等信息,应当予以记录留存。Ⅰ.时间Ⅱ.内容Ⅲ.方式Ⅳ.依据
甲公司为增值税一般纳税人,适用的增值税税率为16%。2016年7月甲公司发生如下业务。(1)1日,与乙公司签订委托代销合同,委托乙公司销售N商品2000件,合同约定乙公司按每件100元对外销售。甲公司按售价的10向乙公司支付手续费(手续费不考虑
Thebestwayoflearningalanguageisusingit.ThebestwayoflearningEnglishistalkinginEnglishasmuchaspossible.Som
JustfiveyearsagoChinesebuyers_______for1%ofglobalsalesofluxurygoods.
最新回复
(
0
)