新教科版-高一信息技术-41-算法及其特征课件.pptx

1、 人类必将生活在一种程序设计的世界里。在这个世界里，人类文化与程序设计不仅并行存在，而且会互相联系，融合 为一种全新的人类思想。叶尔肖夫(Yershow)学习目标熟悉将解决问题的方法归结为一系列清晰、准确的步骤的过程。了解算法的基本要素和重要特征。运用恰当的方式描述算法。运用Python语言实现简单算法，解决问题。学习重点 能够分析问题，设计解决问题的算法，并用恰当的方法描述算法；了解枚举法的含义，并能使用枚举法解决相关问题。学习难点 能够设计出解决问题的算法；能够用枚举法解决相关问题。“一个房间里有3盏灯，房间外有3个开关分别控制这3盏灯，在只允许进房间一次的情况下，如何判断哪个开关控制那盏

2、灯？活动1 寻找“开关对应关系”(P86-P87)图4.1.1 开关对应关系第一步：打开1、2两个开关第二步：过2分钟后关闭1号开关第三步：进房间，亮着的灯是由2号开关控制第四步：摸一下另外两盏不亮的灯，发热的灯泡是由1号开关控制第五步：不亮又不热的灯是由3号开关控制小组讨论后 设计算法是解决问题的核心，它的基本任务是对问题进行定性分析和定量分析，遵循算法的特征和约定，寻求计算的方法和规则，明确解决问题的途径。从表面上看，灯只有亮、灭两种状态，但是灯又具有一种特殊性，即开灯的同时会伴随发光发热，因此灯被触摸时还有冷、热两种状态。综上所述，一盏灯可能有4种不同的状态。而在房间内共有3盏灯，完全可

3、以保证每盏灯的状态都是唯一的。由于题目中并没有限制开关按动次数，所以3个开关的闭合状态是可以随意改变的。如何能使3盏灯处于不同的状态?请在下框中写下你的步骤，在小组中比比谁的方法更快捷、更合理。第一步:第二步:.归纳有效解决问题的具体步骤，对问题进行定性分析和定量分析，就能得出答案。首先开1号、2号两个开关，2分钟后关闭1号开关，然后进房间，显然亮着的灯由2号开关控制。接下来摸一下另外两盏不亮的灯，发热的灯肯定由1号开关控制。最后确定3号开关控制的灯。完善“开关对应关系”流程图完善“开关对应关系”流程图关关1 1号开关号开关灯亮？灯亮？灯热？该灯由该灯由2 2号开关控制号开关控制该灯由该灯由1

4、 1号开关控制号开关控制该灯由该灯由3 3号开关控制号开关控制算法的特征学生思考：根据解决“被删除的ID号”算法中的一些规律，思考算法应该具有哪些特征。填写下表。现象（可多选）现象（可多选）算法的特征算法的特征输入项：输入项：0个输入 1个输入 多个输入输出项：输出项：0个输出 1个输出 多个输出执行的结果：执行的结果：确定的 不确定的 都可以执行的步骤：执行的步骤：有限 无限 都可以执行的时间：执行的时间：有限 无限 都可以算法的重要特征有穷性有穷性 算法必须能在执行有限个步骤之后终止。确切性确切性 算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。输入项输入项

5、 一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输人是指算法本身给出了初始条件。输出项输出项 算法一定要有输出。任何算法都不能“无功而返”。可行性可行性 算法中执行的任何计算都可以在有限时间内完成(也称为有效性)。算法中的运算都必须是可以实现的。从某种意义上说，算法也是一种数学模型。一般而言，问题求解的第一步是数学建模。用数学语言描述实际现象，将现实世界的问题抽象成数学模型，就可能发现问题的本质并判定其能否求解，继而找到求解该问题的方法和算法。现象（可多选）现象（可多选）算法的特征算法的特征输入项：输入项：0个输入 1个输入 多个输入0个或多个输入项输出项：输出项：0个输出 1个

6、输出 多个输出1个或多个输出项执行的结果：执行的结果：确定的 不确定的 都可以算法的确定性执行的步骤：执行的步骤：有限 无限 都可以算法的有穷性执行的时间：执行的时间：有限 无限 都可以算法的可行性算法的特征：代码描述算法代码描述算法For I=1 to N if n能被3、5、7整除余数为2、3、2 then 输出n exit for end ifnext算法及其表示方法 1、算法描述的方法：自然语言、流程图、伪代码 2、用自然语言来描述算法：缺点：繁琐冗长、容易出现“歧义性”、优点：用自然语言描述顺序执行的步骤较好懂、比较通俗易懂。例如：韩信点兵的实例算法描述为：step1：将N初始值赋为

7、1step2：如果N被3、5、7整除后的余数分别为2、3、2则输出N的值，转step4step3：将N的值加1，转step2。step4：结束程序。3、用流程图来描述算法：流程图：用图形来表示算法，用它的优点：形象、直观、更容易理解。流程图图例：请同学们设计出“韩信点兵”流程图“韩信点兵”流程图4、用伪代码描述算法介于自然语言和计算机程序语言之间的一种算法描述。优缺点：没有严格的语法限制，书写格式比较自由，关键词用英文单词，描述的算法简洁易懂，容易修改。算法描述直观。5、三种算法对比：自然语言描述与流程图描述比较自然语言描述与流程图描述比较自然语言流程图伪代码伪代码直观清晰直观清晰确定性确定性

8、烦琐程度烦琐程度是否容易修改是否容易修改通俗易懂通俗易懂活动2 定量分析，寻找“被污染的药丸”如图有4个分别装了4种药丸的药瓶，里面每颗药丸都有单颗标准质量，其中有一个药瓶中的所有药丸都被污染了。每颗被污染的要玩比正常的药丸增重1g，请只允许城中一次的情况下，判断哪个药瓶中的药丸被污染了。如果从每个药瓶中取出1颗药丸分别进行称重，肯定可以判断出哪颗药丸被污染了，但是这种做法显然不符合“只能称量一次”的要求。你能改进判断方法吗?活动2 定量分析，寻找“被污染的药丸”考虑1颗药丸的重量变化，如果药丸被污染，则增重_克，否则增重_克。从某一个药瓶中取出n颗药丸，如果被污染，则增重 克，否则增重_克。

9、如果我们从不同的药瓶中取出不同颗数的药丸，你能根据增重情况找出被污染的药丸吗?从第1个药瓶中取出1颗药丸，从第2个药瓶中取出2颗药丸，从第3个药瓶中取出3颗药丸，从第4个药瓶中取出4颗药丸，共10颗药丸。如果增重_克，则_ 号 药瓶中的药丸被污染。回顾算法的特点，思考一下，在这个问题中，哪些信息属于输入、哪些信息属于输出呢?d=int(input(请输入每颗药丸的标准重量：)w=int(input(请输入药丸称得的重量：)x=w-10*d print(被污染的药瓶序号是：,x)input(运行完毕，请按回车键退出.)设计程序并运行，使输入10颗药丸的总重量及4种药丸的单颗标准质量就可以看到结果

10、，找到被污染的药丸。活动3 巧用运算，寻找“误删的ID号”程序设计：学校历届校友的数据存储在学校网络中心服务器中(共10000条，无重复数据)，某管理员由于误操作删除了一位校友的ID号(8位整数)。恰好在备份文件中保存了所有人员的ID号(无重复数据，无序)。怎样快速找出被误删的ID号以便恢复数据?仔细分析问题，我们发现实际需要参与分析及处理的只有ID号，而且这些ID号的特征也很明显。请归纳ID号的特征，写在下面的横线上。D D号的特征号的特征 数据类型及大小范围:数据在两个文件中出现的次数:备份文件中ID号总和与故障文件中的ID号总和的差值为:target=0#设置初始值f1=open(cop

11、y.txt,r)#打开备份文件list1=f1.readlines()#读取每行数据for line in list1:target=target+int(line)#将读取的数据做和运算f1.close()#关闭备份文件f2=open(trouble.txt,r)#打开故障文件list2=f2.readlines()#读取每行数据for line in list2:target=target-int(line)#将读取的数据做减运算 f2.close()#关闭故障文件print(被删除的ID号是:,target)#输出被删除的ID号input(运行完毕，请按回车键退出.)“误删的ID号”代码

12、及流程图运行效果文件打开模式求解谁是冠军？活动尝试枚举活动尝试枚举 这次面试的冠军在A、B、C、D四位同学中。A说:不是我。B说:是C。C说:是D。D说：C说的不对。已知四人中有一人说了假话。你能判断出到底谁是冠军吗?说出你的结论和判断过程。解析：解析：利用枚举法，逐一假设A、B、C、D是冠军，判断是否正确。冠冠 军军 A A说：说：“不是我。不是我。”B B说：说：“是是C C。”C C说：说：“是是D D。”D D说：说：“C C说的不说的不对。对。”ABCD枚 举将这个问题用计算机程序来解决将这个问题用计算机程序来解决：（提示：我们需要把每个人说的话转化成计算机能够执行的表达式。如A说：

13、“不是我。”可以表示为“i!=A”，其中i为枚举的冠军选手编号。解读下面的程序，尤其理解标注横线的语句含义。）枚举我们常利用计算机运算速度快、精确度高的特点解决实际问题。在设计算法时，最简单的方法就是“直译”我们的思维过程。有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作“枚举枚举”或“穷举穷举”在不知道谁说真话、谁说假话的情况下，最简单的方法就是把所有可能都枚举出来。因为只有一位冠军，所以可以枚举选手的编号，并对A、B、C、D四个人的话进行判断。计算的本质是完成一系列算术运算和逻辑运算。因此在进行计算时，首先要将各种类型的数值问题转化为计算机能够执行的基本运算。在

14、本任务中，我们需要把每个人说的话转化成计算机能够执行的表达式。如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)枚 举分析以下代码的含义，理解解题思路，并在横线上填写语句的功能。枚举 champion=A,B,C,D#设置选手列表 for i in champion:#循环读取选手编号 cond=(i!=A)+(i

15、=C)+(i=D)+(i!=D)#查找符合条件的选手 if cond=3:#说真话是否是3人 print(冠军是:,i)#输出冠军 input(运行完毕，请按回车键退出.)有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作“枚举”或“穷举”。枚举法解决问题的一般结构结构：循环+判断。优势优势：易证明正确性枚 举练一练：1.36528=38256，在两个内填入相同的数字使得等式成立。求这个数。for i in range(10):if(i*10+3)*6528)=(30+i)*8256):print(结果是：,i)for i in range(100,1000):if

16、i%3=0:print(i)2.找出三位正整数中能被3整除的整数。3.在一千多年前的孙子算经中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”。即一个数除以3余2，除以5余3，除以7余2，求这个数。i=0while(i%3!=2 or i%5!=3 or i%7!=2):i=i+1 print(i)异或应用于逻辑运算，其运算法则为：00=0，10=1，01=1，11=0。由于两个相同数异或结果为0，而任何数异或0的结果等于数据本身。拓展知识：异或运算拓展知识：华容道 1、历经中外科学家姜长英、藤村幸三郎、清水达雄、马丁加达纳等几十年的努力，游戏解法已由六十多年前的87步减少至81步。2、美国一个律师托马斯.莱曼(Thomas B.Lenann)发现一个新的解法，由加德纳公布在1964年3月科学美国人上，有81步，称加德纳解法。3、华容道的最快走法在中国是100步，在日本是82步。后来美国人用计算机，使用穷举法找出了最终解法，不可能有再快的解法了，81步。美国人在用计算机找到最终解法后，跟中国人开玩笑说美国一位著名的博士找到了最终解法，这位博士名叫computer。