4.1 算法及其特征 ppt课件-新教科版（2019）《高中信息技术》必修第一册.pptx

1、第2单元 编程计算第1单元 初识数据与计算第3单元 认识数据第4单元 计算与问题解决第5单元 数据分析与人工智能信息技术信息技术（必修（必修1 1）4.1 4.1 算法及其特征算法及其特征学习目标 熟悉将解决问题的方法归结为一系列清晰、熟悉将解决问题的方法归结为一系列清晰、准确的步骤准确的步骤的过程。的过程。了解算法的基本要素和重要特征。了解算法的基本要素和重要特征。运用恰当的方式描述算法。运用恰当的方式描述算法。运用运用PythonPython语言实现简单算法，解决问题。语言实现简单算法，解决问题。软件设计师是业务领域和技术领域的专家。面对客户需求，软件设计师要对问题进行软件设计师是业务领域

2、和技术领域的专家。面对客户需求，软件设计师要对问题进行整体分析以找到解决方案，通过洽当的方式与客户沟通；面对技术问题，软件设计师需整体分析以找到解决方案，通过洽当的方式与客户沟通；面对技术问题，软件设计师需要借助计算机编程解决实际问题。我们将通过要借助计算机编程解决实际问题。我们将通过“软件开发社招新软件开发社招新”项目讨论计算机编程项目讨论计算机编程解决问题的过程。解决问题的过程。活动1 寻找“开关对应关系”软件开发社团要招募新成员，报名的同学要经过面试才能加入。第一关面试题是：软件开发社团要招募新成员，报名的同学要经过面试才能加入。第一关面试题是：“一个房间有一个房间有3 3盏灯，房间外有

3、盏灯，房间外有3 3个开关分别控制这个开关分别控制这3 3盏灯在只允许进房间一次的情况下，盏灯在只允许进房间一次的情况下，如何判断哪个开关控制哪盏灯？如何判断哪个开关控制哪盏灯？”设计算法是解决问题的核心，它的基本任务是对问题进行定性分析和定量分析，设计算法是解决问题的核心，它的基本任务是对问题进行定性分析和定量分析，遵循算法的特征和约定，寻求计算的方法和规则，明确解决问题的途径。遵循算法的特征和约定，寻求计算的方法和规则，明确解决问题的途径。任务一 探讨面试题的解决方案分析问题灯的状态和特性 灯只有亮、灭两种状态，但是灯又具有一种特殊性，即开灯的同时会伴随发光发灯只有亮、灭两种状态，但是灯又

4、具有一种特殊性，即开灯的同时会伴随发光发热，因此灯被触摸时还有冷、热两种状态。综上所述，一盏灯可能有热，因此灯被触摸时还有冷、热两种状态。综上所述，一盏灯可能有4 4种不同的状态。种不同的状态。怎么样保证每盏灯的状态都是唯一的？题目中并没有限制开关按动次数，所以3个开关的闭合状态是可以随意改变的。想一想，划一划第一步：打开1、2两个开关第二步：过2分钟后关闭1号开关第三步：进房间，亮着的灯是由2号开关控制第四步：摸一下另外两盏不亮的灯，发热的灯泡是由1号开关控制第五步：不亮又不热的灯是由3号开关控制自然语言流程图关1号开关灯亮？灯热？该灯由2号开关控制该灯由1号开关控制该灯由3号开关控制解决问

5、题的方法及步骤算算法法设计算法计算a,b两数和与差?第一步：输入两个数a,b第二步：计算两数和s1=a+b第三步：计算两数差s2=a-b第四步：输出s1,s2输入两个数a,b计算s1=a+b,s2=a-bPrint s1,s2输入a,bS1=a+bS2=a-b输出s1,s2输入a,bS1=a+b,s2=a-b输出s1,s2算法的描述算法的描述自然语言流程图伪代码N-S框图PAD图程序代码算法的特征算法必须能在执行有限个步骤之后终止。算法必须能在执行有限个步骤之后终止。算法中的每一次运算都有明确的定义，具有无二义性，并且可以算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一

6、的结果。通过计算得到唯一的结果。算法一定要有输出。任何算法都不能算法一定要有输出。任何算法都不能“无功而返无功而返 。输入项。一个算法有输入项。一个算法有0 0个或多个输入，以刻画运算对象的初始悄况，个或多个输入，以刻画运算对象的初始悄况，所谓所谓0 0个输入是指算法本身给出了初始条件。个输入是指算法本身给出了初始条件。算法中执行的任何计算都可以在有限时间内完成（也称为有效性）。算法中执行的任何计算都可以在有限时间内完成（也称为有效性）。有有4 4个分别装了个分别装了4 4种药丸的药瓶，里面每颗药丸都有单颗标准质量，其中有一个药瓶种药丸的药瓶，里面每颗药丸都有单颗标准质量，其中有一个药瓶中的所

7、有药丸都被污染了。中的所有药丸都被污染了。每颗被污染的药丸比正常药丸增重每颗被污染的药丸比正常药丸增重1 1克。请在只允许称量一克。请在只允许称量一次的情况下，判断出哪个药瓶中的药丸被污染了。次的情况下，判断出哪个药瓶中的药丸被污染了。改进算法分析分析现象（可多选）现象（可多选）算法的特征算法的特征哪些信息属于输入：输入项：0个输入 1个输入 多个输入哪些信息属于输出：输出项：0个输出 1个输出 多个输出执行的结果：执行的结果：确定的 不确定的 都可以需要 步得到结果。执行的步骤：有限 无限 都可以题耗时 。执行的时间：有限 无限 都可以标准重量，称重后重量标准重量，称重后重量多出的重量多出的

8、重量找到被污染的瓶子找到被污染的瓶子4几秒几秒0个或多个输入一定有输出确切性有穷性可行性设计算法回顾算法的特点，思考一下，在这个问题中，哪些信息属于回顾算法的特点，思考一下，在这个问题中，哪些信息属于输入输入、哪些信息属于哪些信息属于输出输出呢？呢？d=int(input(d=int(input(请输入每颗药丸的标准重量：请输入每颗药丸的标准重量：)w=int(input(w=int(input(请输入药丸称得的重量：请输入药丸称得的重量：)x=w-10 x=w-10*d dprint(print(被污染的药瓶序号是：被污染的药瓶序号是：,x),x)input(input(运行完毕，请按回车键

9、退出运行完毕，请按回车键退出.).)活动3 巧用运算，寻找误删的ID号”学校历届校友的数据存储在学校网络中心服务器中（共学校历届校友的数据存储在学校网络中心服务器中（共1000010000条，无重复数据），某条，无重复数据），某管理员由于误操作删除了一位校友的管理员由于误操作删除了一位校友的IDID号号(8(8位整数）。恰好在备份文件中保存了所有人位整数）。恰好在备份文件中保存了所有人员的员的IDID号（无重复数据，无序）。怎样快速找出被误删的号（无重复数据，无序）。怎样快速找出被误删的IDID号以便恢复数据？号以便恢复数据？1.ID数据类型：_2.数据在两个文件中出现的次数：_3.备份文件中

10、1D号总和与故障文件中的ID号总和的差值为：_自然语言描述算法第一步第一步：打开备份数据：打开备份数据f1f1与故障数据与故障数据f2f2第二步第二步：读取备份数据：读取备份数据list1list1，并数据求和，并数据求和targettarget第三步第三步：读取故障文件：读取故障文件list2list2，并用备份数，并用备份数据和据和targettarget减去故障数据和减去故障数据和第四步第四步：输出差值，即为误删：输出差值，即为误删IDID号号备份ID号故障ID号设计算法找出被删除的ID 通过分析，我们发现计算备份文件通过分析，我们发现计算备份文件IDID号总和与故障文件号总和与故障文件

11、IDID号总和的号总和的差值就是误删的差值就是误删的IDID号。号。target=_ f1=open(copy.txt,r)listl=fl.readlines()for line in _:target=target+int(line)fl._f2=open(trouble.txt,r)list2=_for _:target=_print(被误删的ID号是：，_)0list1Close()f2.readlines()line in list2target int(line)F2.close()target代码解析 这次面试的冠军在这次面试的冠军在A A、B B、C C、D D四位同学中。四位

12、同学中。A A说：说：“不是我。不是我。”B B说：说：“是是C C”。“C C说：说：“是是D D。”D D说：说：“C C说的不对。说的不对。”已知四人中有一人说了假话。已知四人中有一人说了假话。你你能判断出到底谁是冠军吗？说出你的结论和判断过程。能判断出到底谁是冠军吗？说出你的结论和判断过程。活动尝试枚举不是我是C是DC说的不对ABCD任务二 求解“谁是冠军”枚举 有一种算法是把所有可能的答案一一列举，合适就保留，不合适有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作就丢弃。这种方法称作“枚举枚举”或或“穷举穷举”枚举法解决问题的一般结构：循环枚举法解决问题的

13、一般结构：循环+判断。判断。优势：易证明正确性优势：易证明正确性 在不知道谁说真话、谁说假话的情况下，最简单的方法就是把所在不知道谁说真话、谁说假话的情况下，最简单的方法就是把所有可能都枚举出来。因为只有一位冠军，所以可以枚举选手的编号，有可能都枚举出来。因为只有一位冠军，所以可以枚举选手的编号，并对并对A A、B B、C C、D D四个人的话进行判断。四个人的话进行判断。解析：利用枚举法，逐一假设解析：利用枚举法，逐一假设A A、B B、C C、D D是冠军，判断是否正确。是冠军，判断是否正确。冠冠 军军A A说：说：“不是我。不是我。”B B说：说：“是是C C。”C C说：说：“是是D

14、D。”D D说：说：“C C说的不对。说的不对。”ABCD 用程序求谁是冠军时，我们需要把每个人说的话转化成计算机能够执行的表达式。如用程序求谁是冠军时，我们需要把每个人说的话转化成计算机能够执行的表达式。如A A说：说：“不是我。不是我。”可以表示为可以表示为“i!=A”“i!=A”，其中，其中i i为枚举的冠军选手编号。为枚举的冠军选手编号。设计算法答案答案 冠军是冠军是:C C 在孙子算经中，有这样一道算术题：在孙子算经中，有这样一道算术题：“今有物不知其数，三三数之剩今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？二，五五数之剩三，七七数之剩二，问物几何？”。（即一

15、个数除以即一个数除以3 3余余2 2，除，除以以5 5余余3 3，除以，除以7 7余余2 2，求这个数，求这个数。）。）参考答案：参考答案：i=0while(i%3!=2 or i%5!=3 or i%7!=2):i=i+1 print(i)巩固提升课堂小结算法：解决问题的方法和步骤；算法的描述：算法的特征：有穷性：算法步骤有限；确切行：每一次运算的含义明确；输入项：一个算法有0个或多个输入；输出项：算法一定要有输出；可行性：在有限时间内完成；计算机解决问题的一般过程：自然语言流程图伪代码N-S框图PAD图程序代码具体具体问题问题分析问题分析问题问题问题解决解决设计算法设计算法编写程序编写程序调试运行调试运行