1、 【学习目标】【学习目标】 1.熟悉将解决问题的方法归纳为一系列清晰、准确的步骤的过程。 2.了解算法的基本要素和重要特征。 3.运用恰当的方式描述算法。 4.运用Python语言实现简单的算法。 【教学重点】【教学重点】 能够分析问题，设计解决问题的算法，并用恰当的方法描述算法； 了解枚举法的含义，并能使用枚举法解决相关问题。 【教学难点】【教学难点】 能够设计出解决问题的算法；能够用枚举法解决相关问题。 面试中有一道IQ题：有四个装了药丸的罐子，每个药丸都 有一定的重量，其中有一个药罐被污染了。每片被污染的 药丸比污染前增重1克。只允许称量一次，判断出哪个罐 子的药被污染了。（同座位讨论该
2、问题的解决步骤） 方法： 考虑药丸的质量变化，如果药丸被污染，则增重_克，否则增重 _克。 从任一药瓶中提取n颗药丸，如果增重n克，则_；如果没有增 重，则_ 从第一盒中取出1颗，第二盒中取出2 颗，第三盒中取出3颗，从第 四盒中取出4颗（共10颗）。如果增重_克，则_号药瓶 被污染。 在生活中很多类似的问题，在解决问题过程中都需要有一定方法。这在生活中很多类似的问题，在解决问题过程中都需要有一定方法。这 种问题解决的方法实际就是算法。种问题解决的方法实际就是算法。 1、算法描述的方法 自然语言、流程图、伪代码 2、用自然语言来描述算法： 缺点：繁琐冗长、容易出现“歧义性”、 优点：用自然语言
3、描述顺序执行的步骤较好懂、比较通俗易懂。 例如：韩信点兵的实例 算法描述为： step1：将N初始值赋为1 step2：如果N被3、5、7整除后的余数分别为2、3、2则输出 N的值，转step4 step3：将N的值加1，转step2。 step4：结束程序。 3、用流程图来描述算法： 流程图：用图形来表示算法，用它的优点：形象、直观、更容易理解。 流程图图例： 请同学们设计出 “韩信点兵”流程图 3、用伪代码描述算法 介于自然语言和计算机程序语言之间的一种算法描述。 优缺点：没有严格的语法限制，书写格式比较自由，关键词用英文单词，描述 的算法简洁易懂，容易修改。算法描述直观。 4、三种算法对
4、比： 自然语言描述与流程图描述比较自然语言描述与流程图描述比较 自然语言流程图伪代码伪代码 直观清晰直观清晰 确定性确定性 烦琐程度烦琐程度 是否容易修改是否容易修改 通俗易懂通俗易懂 学校历届校友的海量数据存储在校网络中心服务器中（共 10000条，无重复数据），某管理员因为误操作删除了 一位校友的ID号（8位整数）信息，恰好在备份数据库中 保存了一份所有人员ID号的文件（无重复数据，无序）。 怎样快速找出被误删的ID号以便恢复数据？ 网络中心服务器网络中心服务器ID列表列表备份服务器备份服务器ID列表列表 19750001 19760230 19990002 19990003 199900
5、03 19750001 19760230 20010432 19990002 例如： 请同位讨论，用自然语言描述问题求解的算法。 方法一：方法一： 取出网络中心服务器ID列表中第一条数据；和 备份服务器中的ID列表逐条进行对比，如果能够找到相同 的ID号，则完成目标，否则取出网络中心服务器ID列表中 下一条数据继续比对。 按照该算法解决问题需要按照该算法解决问题需要10000*10000，1亿次。亿次。 方法二：（提示：可以利用异或运算）方法二：（提示：可以利用异或运算） 异或应用于逻辑运算，其运算法则为：异或应用于逻辑运算，其运算法则为：00=0，10=1， 01=1，11=0。 由于两个相
6、同数异或结果为由于两个相同数异或结果为0，而任何数异或，而任何数异或0的结果等的结果等 于数据本身。因此，可以把两文件中所有于数据本身。因此，可以把两文件中所有ID号直接进行异号直接进行异 或，只出现一次的数据就能被找出，并且最后出现的异或或，只出现一次的数据就能被找出，并且最后出现的异或 结果就是这个数。结果就是这个数。 （学生可能会提出将中心服务器的（学生可能会提出将中心服务器的ID号全部加起来，然后号全部加起来，然后 减去备份服务器的减去备份服务器的ID号，得到的数就是被删除的号，得到的数就是被删除的ID号，号， 可以让学生比较它和异或的方法）可以让学生比较它和异或的方法） 1.计算备份
7、库ID号异或结果的循环结构和计算中心库ID号 异或结果的循环结构能不能交换顺序？ 2.如何存放两个数据库中ID号？ 可以交换可以交换 列表、文件、数据库。列表、文件、数据库。 已知备份数据库文件存放在已知备份数据库文件存放在“copy.txt”中，中心服务器文件存放在中，中心服务器文件存放在 “trouble.txt”中，用程序实现该问题的解决。中，用程序实现该问题的解决。 提示：文件的一般使用方法提示：文件的一般使用方法 f1=open(rcopy.txt) #打开文件打开文件 list1=f1.readlines() #读取每行数据，读取每行数据，list1是一个记录了问题所有元素的是一个
8、记录了问题所有元素的 列表列表 f1.close #关闭文件关闭文件 程序如下：程序如下： target=0 #设置初始值 f1=open(rcopy.txt) #打开备份文件 list1=f1.readlines() #读取每行数据 for line in list1: #依次处理列表list1中的数据 target= targetint(line) #将读取的数据做异或运算 f1.close #关闭备份文件 f2=open(rtrouble.txt) #打开故障文件 list2=f2.readlines() #按行读取故障文件 for line in list2: #依次处理列表list2
9、中的数据 target= targetint(line) #将读取的数据做异或运算 f2.close #关闭备份文件 print(被删除的ID号是:, target) #输出被删除的ID号 学生思考：学生思考：根据解决“被删除的ID号”算法中的一些规律， 思考算法应该具有哪些特征。填写下表。 现象（可多选）现象（可多选）算法的特征算法的特征 输入项：输入项： 0个输入个输入 1个输入个输入 多个输入多个输入 输出项：输出项： 0个输出个输出 1个输出个输出 多个输出多个输出 执行的结果：确定的执行的结果：确定的 不确定的不确定的 都可以都可以 执行的步骤：有限执行的步骤：有限 无限无限 都可以
10、都可以 执行的时间：有限执行的时间：有限 无限无限 都可以都可以 0或多个输入项 1或多个输出项 算法的确定性 算法的有穷性 算法的可行性 任选一种方法表达一道IQ题的解决方法：“房间里有三盏 灯，房间外有三个开关，在房外看不见房内的情况下，进 门一次确定开关与灯的控制关系。” 打开1和2号开关片刻； 关闭2号开关； 进入房间。发现亮的灯对应1 号开关；暗且热的灯对应2号 开关，剩余的灯对应3号开关。 算法的表达方式各有特点。如自然语言算法的表达方式各有特点。如自然语言 表述比较贴近自然方式，表述方便；但表述比较贴近自然方式，表述方便；但 容易有二义性，流程图表示比较清晰，容易有二义性，流程图
11、表示比较清晰， 但绘制起来比较麻烦；程序功能强大，但绘制起来比较麻烦；程序功能强大， 编写有一定难度。三种方式可以根据实编写有一定难度。三种方式可以根据实 际问题进行选择。只要恰当准确即可。际问题进行选择。只要恰当准确即可。 在程序设计中常见的算法有解析法解析法，例如：求解二元一次方 程，输入方程的系数a，b，c，然后利用求根公式求出方程 的解。再比如枚举法枚举法，利用了计算机运算速度快、精确度高 的特点，把所有可能的答案一一列举，合适就保留，不合适 就丢弃。这种方法也称作“枚举”或“穷举”。 例题：例题：叶达班上有好几位志同道合的软件开发爱好者。听说这 次面试的冠军就在叶达班的A、B、C、D
12、四位同学中。消息很 快传到了班上，当A、B、C、D四人回到班上，叶达迫不及待 地问他们中谁得了冠军。四人相对一笑，A说：“不是 我。”B说：“是C。”C说：“是D。”D说：“C说的不 对。”原来他们想让叶达猜出答案，而且有一人说了假话。叶 达很快就知道了答案，大家都想知道他的方法。你能判断到底 谁是冠军吗？ 解析：解析：利用枚举法，逐一假设A、B、C、D是冠军，判断 是否正确。 冠军冠军A说：说：“不是我。不是我。”B说：说：“是是C。”C说：说：“是是D。”D说：说：“C说的不对。说的不对。” A B C D 将这个问题用计算机程序来解决将这个问题用计算机程序来解决：（提示：我们需要把每个人
13、说的话 转化成计算机能够执行的表达式。如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(冠军是冠军是:,i) 判断判断每个人说的话是否是真的，每个人说的话是否是真的， 如果是真的表达式为如果是真的表达式为1。cond等等 于几，就表示就几个人说的是真于几，就表示就几个人说的是真 话。话。 枚举每一个选手是冠军。枚
14、举每一个选手是冠军。 运行结果运行结果： 冠军是冠军是C 任选两题完成。 1.36528=38256，在两个内填入相同的数字使得等式 成立。求这个数。 2.找出三位正整数中能被3整除的整数。 3.在一千多年前的孙子算经中，有这样一道算术题：“今有物不 知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几 何？”。即一个数除以3余2，除以5余3，除以7余2，求这个数。 参考答案：参考答案： 1. for i in range(10): if (i*10+3)*6528)=(30+i)*825 6): print(结果是：,i) 2. for i in range(100,1000): if i%3=0: print(i) 3. i=0 while (i%3!=2 or i%5!=3 or i%7!=2): i=i+1 print(i)
