导线和开关.docx

回专题模式回学习阶段模式【题目名称、来源】导线和开关 switch, pas (fl995Toi.-5【问题描述】女叭图5. 6 1)所示，具有3根导线的电缆把A区和B区连接起来。在A区3根导线标以1, 2, 3;在B 区导线1和3被连到开关3,导线2连到开关lo2,. mo在B区有m个开关，标为1,每个开关或处于接通或处于断开probe) P在A区进行测试：如果探头点L才会点亮。一般说来，电缆含血(1 <m W 90)根导线，在A区标以1,2,.m。每一根导线都被严格地连到这些开关中的某一个上 每一个开关上可以连有0根或多根导线。测量：你的程序应作某些测量来确定，导线和开关怎样连。状态，开关的初始状态为断开。我们可用一个探头(到某根导线上，当且仅当该导线连到处接通状态的开关时，灯你的程序从标准输入(sta ndard in put)读入一行以得到数字m ;然后可以通过向标准输出(standardoutput)写入一行以发出命令(共3种命令)。每种命令的开头是一个大写字母0测试导线命令T:T后面跟一个导线标号； 0改变开关状态命令C:C后面跟一个开关标号;。完成命令D:D后面跟的是一个表列(LIST ),该表列中的第i个元素代表与导线i相连的开关号。在命令T和C之后，你的程序应从标准输入(sta ndard in put)读入一行。若开关状态能使灯亮，则命令 T的回答应是Y;反之，回答应是N。命令C的作用是改变开关的状态(若原来是接通则变为断开；若原来是断开则 变为接通)。对C命令的回答是作为一种反馈信号。你的程序可以给出一系列命令，将T命令与C命令以任意顺序混合使用。最后给出命令D,并结束。你的程序给出的命令总数应不大于900ostan dard in put )和标准输出(CRT 单元(unit CRT)o8条命令的对话。sta ndard为了在此任务中能正确使用标准输入( output) o若你使用pascal,请不要使用其中的 举例F图给出了一个实例，对应于上图，这是一个有Stan dard OutputStan dard In putC3T 1T 2T 3C 3C 2T 2D 3 1 33YY NYNYN【所属专题】二分法、递归、交互式【适合学习阶段】第二阶段、第三阶段【解题思路】问题分信息学奥林匹克题解精编要准确的估算你的算法在最差的情况下可能发出命令的总数最多是多少，然后可以发现，仅仅对开关使用二分法还是不能够满足要求（命令数<900 ） o这就启发我们将开关和导线同时使用二分法相结合：所有待连接的导线分为两个集合x,yo x初始化为x=L.m, y二口；然后是开关的二分，查找是一分为二的进行的。当前待连接的所有开关被我们近似平均得分为两 部分，前一半开后一半关。用C命令将前一半开关的状态改变，用T命令对对初始化了的集合x中的导线（即所有当前待连接的导线）测试，根据当前前一半开关的状态和终端的反应，将x的一部分移到y中去，使x中含有的导线一定接在前一半开关中，y中含有的导线一定连在后一半那开关中，这就将待连接的导线分为两部分，然后将前一半开关和x看作子问题进行递归调用操作，知道剩下一个开关就将所有当前待连接的导线接到这个开关 上，或者是当前待连接的导线集合为空。存储结构：集合【测试数据】【源程序】