在一条笔直公路一边有许多房子，现要安装消防栓，每个消防栓覆盖范围远大于房子面积，如下图所示。现求解能覆盖所有房子最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上点）。该问题求解算法基本思路为：从左端第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖所有房子。在剩余房子中重复上述操作，直到所有房子被覆盖。算法采用设计策略为（ ）；对应时间复杂度为（ ）。
假设公路起点A坐标为0，消防栓覆盖范围（半径）为20米，10栋房子坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（请作答此空）个消防栓。以下关于该求解算法叙述中，正确是（ ）。
- A.4
- B.5
- C.6
- D.7
正确答案及解析
正确答案
解析
对于第一空，本题使用是分治法。1、分治法特征：对于一个规模为n问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题解合并得到原问题解。2、动态规划法：在求解问题中，对于每一步决策，列出各种可能局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。本题情景没有列出所有可能解进行筛选，因此，本题不属于动态规划法。3、回溯法：回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走技术就是回溯法。本题情景没有探索和回退过程，因此，本题不属于回溯法。4、贪心法：总是做出在当前来说是最好选择，而并不从整体上加以考虑，它所做每步选择只是当前步骤局部最优选择，但从整体来说不一定是最优选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意解，但得不到最优解。在本题情景中，没有给出每步选择局部最优判断条件，因此，本题属于贪心法。 由于本题算法过程，是依次与各个房子进行判断，当所有房子都被比较之后，则问题结束，因此时间复杂度与房子个数相关，本问题时间复杂度应该趋于现象，为O(n)。对于第三空，关于对应序列（10，20，30，35，60，80，160，210，260，300）第一轮放置：在第一座房子x=10右侧20米处安装一个消防栓，可以覆盖10，20，30，35这4栋房子；2、第二轮放置：去掉前4栋房子，在第5栋房子x=60右侧20米处安装一个消防栓，可以覆盖60、80这2栋房子；3、第三轮放置：去掉前面已覆盖房子，在第7栋房子x=160右侧20米处安装一个消防栓，只可以覆盖160这一栋房子；4、第四轮放置：去掉前面已覆盖房子，在第8栋房子x=210右侧20米处安装一个消防栓，可以覆盖210这一栋房子第五轮放置：去掉前面已覆盖房子，在第9栋房子x=260右侧20米处安装一个消防栓，可以覆盖260、300这2栋房子；房子全部覆盖完毕，因此共需安装5个消防栓。对于第四空，对于得到一个最优解是动态规划特点，可以得到问题所有最优解，是回溯法特征，可以排除A、B选项。对于C、D选项。A.肯定可以求得问题一个最优解B.可以求得问题所有最优解C.对有些实例，可能得不到最优解D.只能得到近似最优
你可能感兴趣的试题
阅读下列说明，冋答问题1至问题3，将解答填入答题纸对应栏内。【说明】某水果零售超市拟开发一套信息系统，对超市顾客、水果、员工、采购和销售信息进行管理。(1)水果零售超市实行会员制，顾客需具有会员资格才能进行购物，顾客需持所在单位出具证明信才能办理会员资格，每位顾客具有唯一编号。(2)超市将采购员和导购员分成若干个小组，每组人员负责指定若干种水果采购和导购。每名采购员可采购指定给该组购买水果；每名导购员都可对顾客选购本组内各种水果进行计价和包装，并分别贴上打印条码。(3)顾客选购水果并计价完毕后进行结算，生成结算单。结算单包括流水号、购买各种水果信息和顾客信息等，每张结算单具有唯一流水号。(4)超市在月底根据结算单对导购员进行绩效考核，根据采购情况对采购员进行考核，同时也根据结算单对顾客消费情况进行会员积分。初步设计数据库关系模式如下。
"结算单"示例如表所示：
【问题1】
对于"顾客"关系模式，请回答以下问题：(1)给出所有候选键。(2)该关系模式可达到第几范式，用60字以内文字简要叙述理由。【问题2】对于"结算单"关系模式，请回答以下问题：(1)用100字以内文字简要说明它会产生什么问题。(2)将其分解为第3范式，分解后关系名依次为：结算单1，结算单2，结算单3，并用下划线标注分解后各关系模式主键。【问题3】对于"职责"关系模式，请回答以下问题：(1)它是否为第4范式，用100字以内文字叙述理由。(2)将其分解为第4范式，分解后关系名依次为：职责1，职责2，┄。
- 查看答案
阅读下列说明，回答问题1至问题3；将解答填入答题纸对应栏内。【说明】某社会救助基金会每年都会举办多项社会公益救助活动，需要建立信息系统，对之进行有效管理。【需求分析】1.任何一个实名认证个人或者公益机构都可以发起一项公益救助活动，基金会需要记录发起者信息。如果发起者是个人，需要记录姓名、身份证号和一部电话号码；如果发起者是公益机构，需要记录机构名称、统一社会信用代码、一部电话号码、唯一法人代表身份证号和法人代表姓名。一个自然人可以是多个机构法人代表。2.公益救助活动需要提供详实资料供基金会审核，包括被捐助人姓名、身份证号、一部电话号码、家庭住址。3.基金会审核并确认项目后，发起公益救助个人或机构可以公开宣传井募捐，募捐得到款项进入基金会账户。4.发起公益救助个人或机构开展救助行动，基金会根据被捐助人所提供医疗发票或其它信息，直接将所筹款项支付给被捐助者。5.救助发起者针对任一被捐助者公益活动只能开展一次。【逻辑结构设计】根据上述需求，设计出如下关系模式:公益活动(发起者编号，被捐助者身份证号，发起者电话号码，发起时间，结束时间，募捐金额)，其中对于个人发起者，发起者编号为身份证号；对于机构发起者，发起者编号为统一社会信用代码。个人发起者（姓名，身份证号，电话号码）机构发起者(机构名称，统一社会信用代码，电话号码，法人代表身份证号，法人代表姓名)被捐助者（姓名，身份证号，电话号码，家庭住址)【问题1】 对关系"机构发起者"，请回答以下问题:(1) 列举出所有候选键。(2) 它是否为3NF ，用1100字以内文字简要叙述理由。(3) 将其分解为 BC 范式，分解后关系名依次为：机构发起者1，机构发起者 2 ，...， 并用下划线标示分解后各关系模式主键。【问题2】对关系"公益摇动 "，请回答以下问题：(1)列举出所有候选键。(2) 它是否为2NF ，用100字以内文字简要叙述理由。(3)将其分解为 BC 范式，分解后关系名依次为:公益活动1，公益活动 2 ，...， 并用下划线标示分解后各关系模式主键。【问题3】基金会根据被捐助人提供医疗发票或其它信息，将所筹款项支付给被捐助者。可以存在分期多次支付情况，为了统计所筹款项支付情况（详细金额和时间) ,试增加"支付记录"关系模式，用100字以文字简要叙述解决方案。
- 查看答案
阅读下列说明，冋答问题1至问题3,将解答填入答题纸对应栏内。【说明】某图书馆管理系统部分需求和设计结果描述如下：图书馆主要业务包括以下几项：(1)对所有图书进行编目，每一书目包括ISBN号、书名、出版社、作者、排名，其中一部书可以有多名作者，每名作者有唯一一个排名；(2)对每本图书进行编号，包括书号、ISBN号、书名、出版社、破损情况、存放位置和定价，其中每一本书有唯一编号，相同ISBN号书集中存放，有相同存储位置，相同ISBN号书或因不同印刷批次而定价不同；(3)读者向图书馆申请借阅资格，办理借书证，以后凭借书证从图书馆借阅图书。办理借书证时需登记身份证号、姓名、性别、出生年月日，并交纳指定金额押金。如果所借图书定价较高时，读者还须补交押金，还书后可退还所补交押金；(4)读者借阅图书前，可以通过ISBN号、书名或作者等单一条件或多条件组合进行查询。根据查询结果，当有图书在库时，读者可直接借阅；当所查书目所有图书己被他人借走时，读者可进行预约，待他人还书后，由馆员进行电话通知；(5)读者借书时，由系统生成本次借书唯一流水号，并登记借书证号、书号、借书日期，其中同时借多本书使用同一流水号，每种书目都有一个允许一次借阅借书时长，一般为90天，不同书目有不同借书时长，并且可以进行调整，但调整前所借出书，仍按原借书时长进行处理；(6)读者还书时，要登记还书日期，如果超出借书时长，要缴纳相应罚款；如果所还图书由借书者在持有期间造成破损，也要进行登记并进行相应罚款处罚。初步设计该图书馆管理系统，其关系模式如图4-1所示。
【问题1】对关系"借还"，请回答以下问题：(1)列举出所有候选键；(2)根据需求描述，借还关系能否实现对超出借书时长情况进行正确判定？用60字以内文字简要叙述理由。如果不能,请给出修改后关系模式（只修改相关关系模式属注时，仍使用原关系名，如需分解关系模式，请在原关系名后加1，2，…等进行区别)。【问题2】对关系"图书"，请回答以下问题：(1)写出该关系函数依赖集；(2)判定该关系是否属于BCNF，用60字以内文字简要叙述理由。如果不是，请进行修改，使其满足BCNF,如果需要修改其它关系模式，请一并修改，给出修改后关系模式（只修改相关关系模式属性时，仍使用原关系名，如需分解关系模式，请在原关系名后加1，2，...进行区别）。【问题3】对关系"书目"，请回答以下问题：(1)它是否属于第四范式，用60字以内文字叙述理由。(2)如果不是，将其分解为第四范式，分解后关系名依次为：书目1，书目2，…。 如果在解决【问题1】、【问题2】时，对该关系属性进行了修改，请沿用修改后属性。
- 查看答案
阅读下列说明，回答问题1至问题3，将解答填入答题纸对应栏内。【说明】某小区由于建设时间久远，停车位数量无法满足所有业主需要，为公平起见，每年进行一次抽签来决定车位分配。小区物业拟建立一个信息系统，对停车位使用和收费进行管理。【需求描述】（1）小区内每套房屋可能有多名业主，一名业主也可能在小区内有多套房屋。业主信息包括业主姓名、身份证号、房号、房屋面积，其中房号不重复。（2）所有车位都有固定编号，且同一年度所有车位出租费用相同，但不同年份出租费用可能不同。（3）所有车位都参与每年抽签分配。每套房屋每年只能有一次抽签机会。抽中车位业主需一次性缴纳全年车位使用费用，且必须指定唯一汽车使用该车位。（4）小区车辆出入口设有车牌识别系统，可以实时识别进出汽车车牌号。为方便门卫确认，系统还需登记汽车品牌和颜色。【逻辑结构设计】根据上述需求，设计出如下关系模式：业主（业主姓名，业主身份证号，房号，房屋面积）车位（车位编号，房号，车牌号，汽车品牌，汽车颜色，使用年份，费用）【问题1】对关系"业主"，请回答以下词题：（1）给出"业主"关系候选键。（2）它是否为2NF，用60字以内文字简要叙述理由。（3）将其分解为BCNF，分解后关系名依次为：A1,A2，...，并用下划线标示分解后各关系模式主键。【问题2】对关系"车位"，请回答以下问题：（1）给出"车位"关系候选键。 ．（2）它是否为3NF，用60字以内文字简要叙述理由。（3）将其分解为BCNF，分解后关系名依次为：B1,B2，...，并用下划线标示分解后各关系模式主键。【问题3】若临时车辆进入小区，按照进入和离开小区时间进行收费（每小时2元）。试增加"临时停车"关系模式，用100字以内文字简要叙述解决方案。
- 查看答案
阅读下列说明，冋答问题1至问题3,将解答填入答题纸对应栏内。【说明】某地人才交流中心为加强当地企业与求职人员沟通，促进当地人力资源合理配置，拟建立人才交流信息网。【需求描述】1．每位求职人员需填写《求职信息登记表》（如表4-1所示），并出示相关证件，经工作人员审核后录入求职人员信息。表中毕业证书编号为国家机关统一编码，编号具有唯一性。每个求职人员只能填写一部联系电话。2．每家招聘企业需填写《招聘信息登记表》（如表4-2所示），并出示相关证明及复印件，经工作人员核实后录入招聘企业信息。表中企业编号由系统自动生成，每个联系人只能填写一部联系电话。3．求职人员和招聘企业基本信息会在系统长期保存，并分配给求职人员和招聘企业用于登录用户名和密码。求职人员登录系统后可登记自己从业经历、个人简历及特长，发布自己求职意向信息；招聘企业工作人员登录系统后可维护本企业基本信息，发布本企业岗位需求信息。4．求职人员可通过人才交流信息网查询企业招聘信息并进行线下联系；招聘企业工作人员也可通过人才交流信息网查询相关求职人员信息并进行线下联系。5．求职人员入职后应惨改自己就业状态（在岗／求职）；招聘企业在发布需求岗位有人员到岗后也应该及时修改需求人数。
【逻辑结构设计】
根据上述需求，设计出如下关系模式：个人信息（身份证号，姓名，性别，出生日期，毕业院校，专业名称，学历，毕业证书编号，联系电话，电子邮件，个人简历及特长）从业经历（身份证号，起止时间，企业名称，职位）求职意向（身份证号，职位名称，最低薪水）企业信息（企业编号，企业名称，地址，企业网址，联系人，联系电话，电子邮件，企业简介）岗位需求（企业编号，职位，专业，学历，薪水，人数，备注）【问题1】对关系"个人信息"，请回答以下问题：(1)列举出所有候选键。(2)它是否为3NF，用60字以内文字简要叙述理由。(3)将其分解为BC范式，分解后关系名依次为：个人信息1，个人信息2，…，并用下划线标示分解后各关系模式主键。【问题2】对关系"企业信息"，请回答以下问题：(1)列举出所有候选键。(2)它是否为2NF，用60字以内文字简要叙述理由。(3)将其分解为BC范式，分解后关系名依次为：企业信息1，企业信息2，…，并用下划线标示分解后各关系模式主键。【问题3】若要求个人求职信息一经发布，即由系统自动查找符合求职要求企业信息，填入表R(身份证号，企业编号)，在不修改系统应用程序前提下，应采取什么方法来实现，用100字以内文字简要叙述解决方案。
- 查看答案