教科版 高一信息技术 必修1 第四单元 4.1 算法及特征 教学设计.pdf

教科版 高一信息技术 必修 1 第四单元 4.1 算法及特征 教学设计4.14.1 算法及其特征算法及其特征【学习目标】【学习目标】1.通过解决开关问题，能够分析出算法的基本特征，感受算法在解决问题中的重要性。2.通过解决药丸问题，尝试运用恰当的方法描述算法。3.能够将部分简单算法转换为程序，并调试运行得出结果。4.通过解决冠军问题，了解枚举法的含义，并能使用枚举法解决相关问题。【教学重点】【教学重点】能够分析问题，设计解决问题的算法，并用恰当的方法描述算法；了解枚举法的含义，并能使用枚举法解决相关问题。【教学难点】【教学难点】能够设计出解决问题的算法；能够用枚举法解决相关问题。【教学过程】【教学过程】第一课时第一课时一、引入一、引入师：师：叶达报名参加学校软件开发社团时。面试中有一道IQ 题：有四个装了药丸的罐子，每个药丸都有一定的重量，其中有一个药罐被污染了。每片被污染的药丸比污染前增重1 克。只允许称量一次，判断出哪个罐子的药被污染了。（同座位讨论该问题的解决步骤）生：生：用自然语言描述问题解决的步骤。第一步：第二步：师：师：在生活中很多类似的问题，在解决问题过程中都需要有一定方法。这种问题解决的方法实际就是算法。二、算法及其表示方法二、算法及其表示方法师：师：算法的定义在 2.1 节已经学过了，请大家再回顾一下，算法的表示方法有几种。生：生：自然语言、流程图、程序。师：师：来看下面这个问题的解决。学校历届校友的海量数据存储在校网络中心服务器中（共10000 条，无重复数据），某管理员因为误操作删除了一位校友的 ID 号（8 位整数）信息，恰好在备份数据库中保存了一份所有人员 ID 号的文件（无重复数据，无序）。怎样快速找出被误删的 ID 号以便恢复数据？例如：网络中心服务器 ID 列表19750001197602301999000219990003备份服务器 ID 列表1999000319750001197602302001043219990002请同座位讨论，用自然语言描述问题求解的算法。生：生：取出网络中心服务器ID 列表中第一条数据；和备份服务器中的ID 列表逐条进行对比，如果能够找到相同的 ID 号，则完成目标，否则取出网络中心服务器ID 列表中下一条数据继续比对。师：师：最差情况下，按照该算法解决问题需要进行多少次比较？1/6教科版 高一信息技术 必修 1 第四单元 4.1 算法及特征 教学设计生：生：10000*10000，1 亿次。师：师：还有没有其他方法？（提示：可以利用异或运算）异或应用于逻辑运算，其运算法则为：00=0，10=1，01=1，11=0。由于两个相同数异或结果为0，而任何数异或0 的结果等于数据本身。因此，可以把两文件中所有 ID 号直接进行异或，只出现一次的数据就能被找出，并且最后出现的异或结果就是这个数。（学生可能会提出将中心服务器的ID 号全部加起来，然后减去备份服务器的 ID 号，得到的数就是被删除的 ID 号，可以让学生比较它和异或的方法）请重新思考该问题解决的算法，并用流程图表示出来。（可以用表示异或）生：图 1师：请师：请思考下面的问题。1.计算备份库ID号异或结果的循环结构和计算中心库ID号异或结果的循环结构能不能交换2/6教科版 高一信息技术 必修 1 第四单元 4.1 算法及特征 教学设计顺序？2.如何存放两个数据库中ID 号？生：生：1.可以交换；2.列表、文件、数据库。师：师：已知备份数据库文件存放在“copy.txt”中，中心服务器文件存放在“trouble.txt”中，用程序实现该问题的解决。提示：文件的一般使用方法f1=open(rcopy.txt)#打开文件list1=f1.readlines()#读取每行数据，list1 是一个记录了问题所有元素的列表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 中的数据 target=targetint(line)#将读取的数据做异或运算f2.close#关闭备份文件print(被删除的 ID 号是:,target)#输出被删除的 ID 号三、算法的特征三、算法的特征师：师：思考解决“被删除的 ID 号”算法中的一些规律，思考算法应该具有哪些特征。填写下表。现象（可多选）输入项：0 个输入1 个输入多个输入输出项：0 个输出1 个输出多个输出执行的结果：确定的不确定的都可以执行的步骤：有限无限都可以执行的时间：有限无限都可以算法的特征生：生：注意对输出的理解。四、总结四、总结算法的特征：0 或多个输入项；1 或多个输出项；算法的确定性（确定的执行结果或者运算的确定性）；算法的有穷性；算法的可行性。第二课时第二课时一、复习一、复习师：师：回顾上一节课的内容，回答算法具有哪些特征？生：生：输入项、输出项、确定性、有穷性、可行性等。师：师：算法的常见表达方式有哪些？生：生：自然语言、流程图、程序。练习：练习：任选一种方法表达一道 IQ 题的解决方法：“房间里有三盏灯，房间外有三个开关，3/6教科版 高一信息技术 必修 1 第四单元 4.1 算法及特征 教学设计在房外看不见房内的情况下，进门一次确定开关与灯的控制关系。”生：生：打开 1 和 2 号开关片刻；关闭 2 号开关；进入房间。发现亮的灯对应 1 号开关；暗且热的灯对应 2 号开关，剩余的灯对应 3 号开关。或者：师：师：为什么同学们不用程序来表示呢？生：生：不方便。师：师：算法的表达方式各有特点。如自然语言表述比较贴近自然方式，表述方便；但容易有二义性，流程图表示比较清晰，但绘制起来比较麻烦；程序功能强大，编写有一定难度。三种方式可以根据实际问题进行选择。只要恰当准确即可。除了已经介绍的三种，其实表达方式还有很多，例如拓展知识中介绍的PAD 表示方法，有兴趣的同学可以课后阅读。二、枚举法二、枚举法师：师：每一个问题都要从头开始思考，比较困难，有没有一些“公式”可以套用呢？在程序设计中常见的算法有解析法，例如：求解二元一次方程，输入方程的系数a，b，c，4/6教科版 高一信息技术 必修 1 第四单元 4.1 算法及特征 教学设计然后利用求根公式求出方程的解。再比如枚举法，利用了计算机运算速度快、精确度高的特点，把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法也称作“枚举”或“穷举”。例题：例题：叶达班上有好几位志同道合的软件开发爱好者。听说这次面试的冠军就在叶达班的A、B、C、D 四位同学中。消息很快传到了班上，当 A、B、C、D 四人回到班上，叶达迫不及待地问他们中谁得了冠军。四人相对一笑，A 说：“不是我。”B 说：“是 C。”C 说：“是 D。”D 说：“C 说的不对。”原来他们想让叶达猜出答案，而且有一人说了假话。叶达很快就知道了答案，大家都想知道他的方法。你能判断到底谁是冠军吗？生：生：利用枚举法，逐一假设A、B、C、D 是冠军，判断是否正确。冠军ABCDA 说：“不是我。”B 说：“是 C。”C 说：“是 D。”D 说：“C 说的不对。”师：师：下面将这个问题用计算机程序来解决。提示：我们需要把每个人说的话转化成计算机能够执行的表达式。如 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.枚举每一个选手是冠军。2.判断每个人说的话是否是真的，如果是真的表达式为 1。cond 等于几，就表示就几个人说的是真话。三、练习三、练习任选两题完成。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)*8256):print(结果是：,i)2.for i in range(100,1000):if i%3=0:print(i)3.5/6教科版 高一信息技术 必修 1 第四单元 4.1 算法及特征 教学设计i=0while(i%3!=2 or i%5!=3 or i%7!=2):i=i+1print(i)6/6