1、4.1算法及其特征第4单元 计算与问题解决学学 习习 目目 标标。（重点）（重点）面试第一题：“一个房间里有3盏灯，房间外有3个开关分别控制这3盏灯，在只允许进房间一次的情况下，如何判断哪个开关控制那盏灯？任务一 活动1 寻找“开关对应关系”(P86-P87)图4.1.1 开关对应关系第一步：第二步：第三步：第四步：第五步：小组讨论后，写出步骤：第一步：打开1、2两个开关第二步：过2分钟后关闭1号开关第三步：进房间，亮着的灯是由2号开关控制第四步：摸一下另外两盏不亮的灯，发热的灯泡是由1号开关控制第五步：不亮又不热的灯是由3号开关控制步骤如下：完善“开关对应关系”流程图关关1 1号开关号开关灯
2、亮？灯亮？灯热？该灯由该灯由2 2号开关控制号开关控制该灯由该灯由1 1号开关控制号开关控制该灯由该灯由3 3号开关控制号开关控制1.1.有穷性有穷性 算法必须能在执行有限个步骤后终止。2.2.确切性确切性 算法中的每次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。3.3.输入项输入项 一个算法有0个或多个输入，所谓0个输入是指算法本身给出了初始条件。4.4.输出项输出项 算法一定要有输出。至少产生一个输出。5.5.可行性可行性 算法中执行的任何计算都可以在有限时间内完成（有效性），算法中的运算都必须是可以实现的。算法的特征算法的特征代码描述算法代码描述算法For I=1
3、to N if n能被3、5、7整除余数为2、3、2 then 输出n exit for end ifnextFor I=1 to N if n能被3、5、7整除余数为2、3、2 then 输出n exit for end ifnext 面试第二题：有4个分别装了4种药丸的药瓶，每颗药丸都有单颗标准质量，其中有一个药瓶中的所有药丸都被污染了。每颗被污染的药丸比正常药丸增重1克。只允许称量一次，请判断出哪个药瓶中的药被污染了。互相讨论该问题的解决步骤，试将P89横线补充完整。任务一 活动2 寻找“被污染的药丸”(P88-P89)任务一 活动3 寻找“误删的ID号”(P89-P90)面试第三题：学
4、校历届校友的数据存储在学校网络中心服务器中(共10000条，无重复数据)，某管理员由于误操作删除了一位校友的ID号(8位整数)。恰好在备份文件中保存了所有人员的ID号(无重复数据，无序)。怎样快速找出被误删的ID号以便恢复数据?误删的误删的 号的流程图号的流程图IDIDtarget=0#设置初始值f1=open(rcopy.txt)#打开备份文件list1=f1.readlines()#读取每行数据for line in list1:#依次处理列表list1中的数据 target=targetint(line)#将读取的数据做异或运算f1.close#关闭备份文件f2=open(rtroubl
5、e.txt)#打开故障文件list2=f2.readlines()#按行读取故障文件for line in list2:#依次处理列表list2中的数据 target=targetint(line)#将读取的数据做异或运算f2.close#关闭备份文件print(被删除的ID号是:,target)#输出被删除的ID号根据流程图及提示信息补充P90代码，结果如下:这次面试的冠军在A、B、C、D四位同学中。A说：“不是我。”B说：“是C。”C说：“是D。”D说：“C说的不对。”已知四人中有一人说了假话。你能判断到底谁是冠军吗？任务二 求解“谁是冠军”枚枚 举举 解析：解析：利用枚举法，逐一假设A、
6、B、C、D是冠军，判断是否正确。冠冠 军军A A说：说：“不是我。不是我。”B B说：说：“是是C C。”C C说：说：“是是D D。”D D说：说：“C C说的不对。说的不对。”ABCD枚枚 举举 用程序求谁是冠军时，我们需要把每个人说的话转化成计算机能够执行的表达式。如A说：“不是我。”可以表示为“i!=A”，其中i为枚举的冠军选手编号。枚枚 举举 分析以下代码的含义，理解解题思路，并在横线上填写语句的功能。champion=A,B,C,D#设置选手列表for i in champion:#_ cond=(i!=A)+(i=C)+(i=D)+(i!=D)#_ if cond=3:print
7、(冠军是:,i)枚枚 举举 请在Python中输入代码并运行程序，看看谁是冠军。答案 冠军是:C枚枚 举举 有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作“枚举”或“穷举”。枚举法解决问题的一般结构结构：循环+判断。优势优势：易证明正确性枚枚 举举1.找出三位正整数中能被7整除的整数。参考答案：参考答案：for i in range(100,1000):for i in range(100,1000):if i%7=0:if i%7=0:print(i)print(i)巩固提升巩固提升2.在一千多年前的孙子算经中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”。即一个数除以3余2，除以5余3，除以7余2，求这个数。参考答案：参考答案：i=0while(i%3!=2 or i%5!=3 or i%7!=2):i=i+1 print(i)巩固提升巩固提升
