（2021新教科版）高中信息技术必修一 4.1 算法及特征教案.docx

1、4.14.1 算法及其特征算法及其特征 【学习【学习目标目标】 1.熟悉将解决问题的方法归纳为一系列清晰、准确的步骤的过程。 2.了解算法的基本要素和重要特征。 3.运用恰当的方式描述算法。 4.运用 Python 语言实现简单的算法。 【教学【教学重点重点】 能够分析问题，设计解决问题的算法，并用恰当的方法描述算法； 了解枚举法的含义，并能使用枚举法解决相关问题。 【教学难【教学难点点】 能够设计出解决问题的算法；能够用枚举法解决相关问题。 【教学过程】【教学过程】 一、引入一、引入 面试中有一道 IQ 题：有四个装了药丸的罐子，每个药丸都有一定的重量，其中有一个 药罐被污染了。每片被污染的

2、药丸比污染前增重 1 克。只允许称量一次，判断出哪个罐子的 药被污染了。 （同座位 讨论该问题的解决步骤）来源:学科网 学生思考：学生思考：用自然语言描述问题解决的步骤？（可小组讨论） 方法：考虑药丸的质量变化，如果药丸被污染，则增重_克，否则增重_克。 从任一药瓶中提取 n 颗药丸， 如果增重 n 克， 则_； 如果没有增重， 则_ 从第一盒中取出 1 颗，第二盒中取出 2 颗，第三盒中取出 3 颗，从第四盒中取出 4 颗 （共 10 颗） 。如果增重_克，则_号药瓶被污染。 在生活中很多类似的问题， 在解决问题过程中都需要有一定方法。这种问题解决的方法实际 就是算法。 二、算法及其表示方法

3、二、算法及其表示方法 1、算法描述的方法： 自然语言、流程图、伪代码 2、用自然语言来描述算法： 缺点：繁琐冗长、容易出现“歧义性” 、 优点：用自然语言描述顺序执行的步骤较好懂、比较通俗易懂。 例如：韩信点兵的实例 算法描述为：step1：将 N 初始值赋为 1 step2： 如果 N 被 3、 5、 7 整除后的余数分别为 2、 3、 2 则输出 N 的值， 转 step4 step3：将 N 的值加 1，转 s tep2。 step4：结束程序。 3、用流程图来描述算法： 流程图：用图形来表示算法，用它的优点：形象、直观、更容易理解。 流程图图例： 例子： “韩信点兵”流程图 开始 1N

4、 N 被 3、5、7 整除后 余数分别为 2、3、2 Y N N+1N 输出 N 的值来源:Zxxk.Com 结束 3、用伪代码描述算法： 介于自然语言和计算机程序语言之间的一种算法描述。 优缺点：没有严格的语法限制，书写格式比较自由，关键词用英文单词，描述的算法 简洁易懂，容易修改。算法描述直观。 4、三种算法对比： 自然语言描述与流程图描述比较 自然语言流程图伪代码 直观清晰 确定性 烦琐程度来源:学科网 是否容易修改 通俗易懂 问题探究：问题探究： 学校历届校友的海量数据存储在校网络中心服务器中（共 10000 条，无重复数据） ，某 管理员因为误操作删除了一位校友的 ID 号（8 位整

5、数）信息，恰好在备份数据库中保存了 一份所有人员 ID 号的文件（无重复数据，无序） 。怎样快速找出被误删的 ID 号以便恢复数 据？ 例如： 网络中心服务器 ID 列表备份服务器 ID 列表 19750001 19760230 19990002 19990003 19990003 19750001 19760230 20010432来源:学_科_网 19990002 请同学们讨论，用自然语言描述问题求解的算法。 方法一：方法一： 取出网络中心服务器 ID 列表中第一条数据；和备份服务器中的 ID 列表逐条进行 对比，如果能够找到相同的 ID 号，则完成目标，否则取出网络中心服务器 ID 列表

6、中下一条 数据继续比对。 按照该算法解决问题需要 10000*10000，1 亿次。 方法二方法二： （提示：可以利用异或运算） 异或应用于逻辑运算，其运算法则为：00=0，10=1，01=1，11=0。 由于两个相同数异或结果为 0，而任何数异或 0 的结果等于数据本身。因此，可以把两 文件中所有 ID 号直接进行异或，只出现一次的数据就能被找出，并且最后出现的异或结果 就是这个数。 （学生可能会提出将中心服务器的 ID 号全部加起来， 然后减去备份服务器的 ID 号， 得到的 数就是被删除的 ID 号，可以让学生比较它和异或的方法） 请重新思考该问题解决的算法，并用流程图表示出来。 （可以

7、用表示异或） 生： 图 1 学生思考：学生思考： 1.计算备份库ID号异或结果的循环结构和计算中心库ID号异或结果的循环结构能不能交换 顺序？ 可以交换可以交换 2.如何存放两个数据库中 ID 号？ 列表、文件、数据库。列表、文件、数据库。 已知备份数据库文件存放在“copy.txt”中，中心服务器文件存放在“trouble.txt”中， 用程序实现该问题的解决。 提示：文件的一般使用方法提示：文件的一般使用方法 f1=open(rcopy.txt)f1=open(rcopy.txt)# #打开文件打开文件 list1=f1.readlines()list1=f1.readlines()# #

8、读取每行数据，读取每行数据，list1list1 是一个记录了问题所有元素的列表是一个记录了问题所有元素的列表 f1.closef1.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

9、()#按行读取故障文件 for line in list2:#依次处理列表 list2 中的数据 target= targetint(line)#将读取的数据做异或运算 f2.close#关闭备份文件 print(被删除的 ID 号是:, target)#输出被删除的 ID 号 三、算法的特征三、算法的特征 学生思考：学生思考：根据解决“被删除的 ID 号”算法中的一些规律，思考算法应该具有哪些特征。 填写下表。 现象（可多选）算法的特征 输入项：0 个输入1 个输入多个输入0 0 或多个输入项或多个输入项 输出项：0 个输出1 个输出多个输出1 1 或多个输出项或多个输出项 执行的结果：确定

10、的不确定的都可以算法的确定性算法的确定性 执行的步骤：有限无限都可以算法的有穷性算法的有穷性 执行的时间：有限无限都可以算法的可行性算法的可行性 练习：练习： 任选一种方法表达一道 IQ 题的解决方法： “房间里有三盏灯，房间外有三个开关，在房外看 不见房内的情况下，进门一次确定开关与灯的控制关系。 ” 打开 1 和 2 号开关片刻； 关闭 2 号开关； 进入房间。发现亮的灯对应 1 号开关；暗且热的灯对应 2 号开关，剩余的灯对应 3 号开 关。 或者： 算法的表达方式各有特点。 如自然语言表述比较贴近自然方式， 表述方便； 但容易有二义性， 流程图表示比较清晰，但绘制起来比较麻烦；程序功能

11、强大，编写有一定难度。三种方式可 以根据实际问题进行选择。只要恰当准确即可。 四、枚举法四、枚举法 在程序设计中常见的算法有解析法解析法，例如：求解二元一次方程，输入方程的系数 a，b，c， 然后利用求根公式求出方程的解。再比如枚举法枚举法，利用了计算机运算速度快、精确度高的特 点，把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法也称作“枚举”或 “穷举” 。 例题例题： 叶达班上有好几位志同道合的软件开发爱好者。 听说这次面试的冠军就在叶达班的 A、 B、C、D 四位同学中。消息很快传到了班上，当 A、B、C、D 四人回到班上，叶达迫不及待 地问他们中谁得了冠军。四人相对一笑，A

12、 说： “不是我。 ”B 说： “是 C。 ”C 说： “是 D。 ”D 说： “C 说的不对。 ”原来他们想让叶达猜出答案，而且有一人说了假话。叶达很快就知道了 答案，大家都想知道他的方法。你能判断到底谁是冠军吗？ 解析：解析：利用枚举法，逐一假设 A、B、C、D 是冠军，判断是否正确。 冠军A 说：“不是我。”B 说：“是 C。”C 说：“是 D。”D 说：“C 说的不 对。” A B C D 将这个问题用计算机程序来解决将这个问题用计算机程序来解决： （提示：我们需要把每个人说的话转化成计算机能够执行 的表达式。如 A 说： “不是我。 ”可以表示为“i!=A” ，其中 i 为枚举的冠军

13、选手编号。 解读下面的程序，尤其理解标注横线的语句含义。 ） champion=A,B,C,D#设置选手列表 for i in champion:#_ cond=(i!=A)+(i=C) + (i=D)+(i!=D) #_ if cond=3: print(冠军是:,i) 1.枚举每一个选手是冠军。 2.判断每个人说的话是否是真的，如果是真的表达式为 1。 cond 等于几，就表示就几个人 说的是真话。 运行结果：冠军是运行结果：冠军是 C C。 练一练：练一练： 任选两题完成。 1.36528=38256，在两个内填入相同的数字使得等式成立。求这个数。 2.找出三位正整数中能被 3 整除的整

14、数。 3.在一千多年前的孙子算经中，有这样一道算术题： “今有物不知其数，三三数之剩二， 五五数之剩三，七七数之剩二，问物几何？” 。即一个数除以 3 余 2，除以 5 余 3，除以 7 余 2，求这个数。 参考答案：参考答案： 来源来源: :学科网学科网 1. for i in range(10): if (i*10+3)*6528)=(30+i)*8256): 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)