首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下算法说明和问题模型图,根据要求回答问题1、问题2。 [说明] 某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点AP(Access Poin)。假设每个无线 AP覆盖范围的半径是6米,因此必须使得每台笔记本电脑上的无线网卡到某个无
阅读以下算法说明和问题模型图,根据要求回答问题1、问题2。 [说明] 某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点AP(Access Poin)。假设每个无线 AP覆盖范围的半径是6米,因此必须使得每台笔记本电脑上的无线网卡到某个无
admin
2013-01-05
25
问题
阅读以下算法说明和问题模型图,根据要求回答问题1、问题2。
[说明]
某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点AP(Access Poin)。假设每个无线 AP覆盖范围的半径是6米,因此必须使得每台笔记本电脑上的无线网卡到某个无线AP的直线距离不超过6米。为了简化问题,假设所有无线网卡在同一直线上,并且无线AP沿该直线放置。该问题可以建模为如图1-13所示,其中直线表示无线网卡所在的直线,实心正方形表示无线网卡。现采用贪心策略实现用尽可能少的无线AP覆盖所有的无线网卡。
实现贪心算法的流程如图1-14所示。其中,①d
(1≤i≤N)表示第i张无线网卡到通道A端的距离,N表示无线网卡的总数,无线网卡的编号按照无线网卡到通道A端的距离从小到大进行编号:②s[k]表示第k(k≥1)个无线AP到通道A端的距离。算法结束后k的值为无线AP的总数。
选项
答案
本试题的题干说明中已将无线网卡分布问题建模(如图1-13所示)。其中,直线表示无线网卡所在的直线,实心正方形表示无线网卡。而要求解的问题是要求如何在该直线上布局无线AP,使其能覆盖所有的无线网卡,并且所用无线AP的数量要尽可能的少。这是一个通过进行一系列选择求最优解的问题。 分析该问题,发现其具有最优子结构,并且具有贪心选择性质,故该问题可以用贪心算法来求解。贪心算法思想是:问题的规模为N,从第1个无线网卡(最左端)开始布局无线AP,把第1个无线AP放置在该无线网卡右方的6米处,此时该无线AP会覆盖从第1个无线网卡到该无线网卡右方直线长度为12米的所有无线网卡,假设覆盖了N1个无线网卡。此时问题规模变成了N-N1,接着把第1个无线AP覆盖的无线网卡去掉,再从N-N1中选择第1个(最左端)无线网卡开始布局无线AP,将第2个无线AP放置在该无线网卡右方的6米处。依此布局,直到覆盖所有的无线网卡。 图1-22是问题解的模型。其中,直线表示无线网卡所在的直线,实心正方形表示无线网卡,实心圆形表示无线AP,虚线圆以对应无线AP为圆心,直径为无线AP的覆盖范围,即对应无线AP的覆盖范围(12米)。 [*] 实现贪心算法的流程见题干的图1-14。由于“算法结束后k的值为无线AP的总数”,因此在算法开始处需要对变量k赋初值,即(1)空缺处所填写的内容是“k=0”。 该贪心算法中,N表示无线网卡的总数,且无线网卡的编号按照无线网卡到通道A端的距离从小到大进行编号,d[i](1≤i≤N)表示第i个无线网卡到通道A端的距离。当判断第i个无线网卡未超过无线网卡总数N,而求解下一个无线网卡(即第i+1个无线网卡,或第j个无线网卡)所归属的无线AP时,也需要判断第j个无线网卡是否超过无线网卡总数N,以及第j个无线网卡与第i个无线网卡之间的距离是否超过12米,因此(2)空缺处所在的判断条件是“j<=N&&d[j]-d[i]<=12”,即该空缺处所填写的内容是“j<=N”或其等价形式。 若第j个无线网卡未超过无线网卡总数N,且第j个无线网卡与第i个无线网卡之间的距离未超过12米,则可以求解再下一个无线网卡(即第i+2个无线网卡,或第j+1个无线网卡)所归属的无线AP。反之,则需要记录无线AP的总数k,即(3)空缺处所填写的内容是“k=k+1”或其等价形式;以及记录第k(k≥1)个无线AP到通道A端的距离,即(4)空缺处所填写的内容是“d[i]+6”或其等价形式。 当求解完第k个无线AP(覆盖了N1个无线网卡)的布局后,需要把第k个无线AP覆盖的无线网卡去掉,再从N-N1中选择第1个(最左端)无线网卡开始布局第k+1个无线AP。依此不断求解,直到覆盖所有的无线网卡。
解析
转载请注明原文地址:https://kaotiyun.com/show/FYDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
下面为C语言程序,边界值问题可以定位在(45)。 int data(3), int i, for(i=1, i<=3, i++)data(i)=100
在软件项目管理中可以使用各种图形工具来辅助决策,下面对甘特(Gantt)图的描述中,不正确的是(15)。
在性能测试中,关于数据准备,(65)描述是正确的。①识别数据状态验证测试案例。②初始数据提供了基线用来评估测试执行的结果。③业务数据提供负载压力背景。④脚本中参数数据真实模拟负载。
用边界值分析法,假定X为整数,10≤X≤100,那么X在测试中应该取(40)边界值。
功能测试执行过后一般可以确认系统的功能缺陷,缺陷的类型包括(37)。①功能不满足隐性需求②功能实现不正确③功能不符合相关的法律法规④功能易用性不好
结构化分析(StructuredAnalysis,SA)是面向数据流的需求分析方法,______不属于SA工具。A.分层的数据流图B.数据词典C.问题分析图D.描述加工逻辑的结构化语言、判定表或判定树
在软件开发过程中,常采用图形表示相关的信息,(28)不用于表示软件模块的执行过程。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的权重表示活动的持续时间(天),则里程碑C在关键路径上。在其他活动按时完成的情况下,活动FJ最多可以晚_______天开始而不影响工期。
给出关系R(A,B,C)和S(A,B,C),R和S的函数依赖集F={A→B,B→C}。若R和S进行自然连接运算,则结果集有3个属性。关系R和S________。
随机试题
A.射干B.鱼腥草C.紫草D.苦参E.蒲公英(1996年第87,88题)功能凉血活血,解毒透疹的药物是()(
中医学认为,甲状腺功能亢进症的基本病理是
医务人员在医疗活动中发生医疗事故争议,应当立即向
根据会计人员回避制度的规定,单位负责人的直系亲属不得在本单位中担任本单位会计机构内的出纳工作。()
我国的人民民主专政实质上是无产阶级专政。
去年1月份,该市进出口贸易总值为()。今年前两个月,一般贸易出口占总出口的比重比去年同期()。
Writingforanhistoricalseriesistricky,andtheoutcomeisnotalwaysasuccess.ThebestoverallEuropeanhistoryinEnglis
用高级程序设计语言编写的程序称为源程序,它
A、 B、 C、 B因为是没有疑问词的疑问句,所以要用以Yes/No开始的句子来回答,又因为问的是竣工时间,所以回答时要包括时间或与此有关的词。(A)是莫名其妙的答复,所以要从正确答案中除去。而(C)所说的是过去已经完成
ThereweremanygreatartistsduringtheRenaissance.PerhapsthemostfamousareLeonardodaVinciandMichelangelo.Otherarti
最新回复
(
0
)