2021-2022学年高中信息技术人教_中图版（2019）必修2.2 算法的概念及描述 课件-（31张PPT）

(共31张PPT)
法
算
The concept and description of the algorithm
2.2算法的概念及其描述
Content
目录
旧知回顾
新知学习
课堂巩固
拓展思考
第一部分
旧知回顾
新知学习
课堂巩固
拓展思考
前课重点
人们解决问题的三个阶段是什么呢？
复习：2.1解决问题的一般过程和用计算机解决问题
计算机解决问题的一般过程又是什么呢？
前课重点
3.解决问题并验证结果
最后，要依据确定的求解方法进行问题解决，考查所得到的解答，通过检验答案和评估效果，实现问题的最终解决。在方案执行过程中，如果发现结果没有达到预期，就需要调整解决方案。
1.分析问题
分析问题主要包括调查、收集与问题相关的资料，明确问题的目标、条件和所涉及的相关知识与规则等，找出已知与未知之间的联系。
2.寻找解决问题的途径与方法
明确要解决的问题后，需要将待解决的问题与已知条件或已有的规则相关联，设计问题求解的方案，包括具体的途径和方法等。
人们解决问题的三个阶段是什么呢？
前课重点
提出问题
分析问题
分析问题
需要把问题进行抽象，通过建模的方式，界定和描述问题。问题描述的方式并不唯一，有的问题可用数学模型描述，有的问题可用文字、表格或图形等形式描述。
编程调试
用计算机程序语言描述算法，实现问题求解。编写完成的程序需要调试，调试不仅要发现错误，分析其产生的原因，进行改正，并对运行的结果进行分析和验证，判断其是否正确和完整。
设计方案
根据需求分析，将问题按照求解过程分解为若干相对独立的功能，每个功能完成一个特定的任务。然后，针对分解的各个特定功能分别进行详细的操作步骤设计，给出问题求解的具体过程和方法。
计算机解决问题的一般过程又是什么呢？
设计方案
编程调试
解决问题
第二部分
旧知回顾
新知学习
课堂巩固
拓展思考
1．列举出由A站出发到达B站的所有换乘次数最少的乘车路线。
2．如果小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线，并说明理由。
想一想：
一、算法的概念
小明同学所在城市的地铁线路局部图，如图所示。他计划从A站出发去B站附近的图书馆学习。假设地铁各线路每两站间行车用时相等，记为t1；换乘地铁的用时也都相等，记为t2
计算机解决问题依靠的是程序，而程序的编写依赖于算法和计算机“语言”， 即首先将需要解决的问题分解为若干个明确的步骤（算法），然后在用计算机能够接受的“语言”准确的描述出来，这样计算机才能够解决问题。
计算机如何解决实际问题？
这里输入简单的文字概述
这里输入简单的文字概述
点击添加标题
一、算法的概念
大家用列举的办法解决了这个问题，如果可能性更多问题更复杂，怎么办？
算法
输入
计算机
枚举法/穷举法
算法是什么？
在学习和生活中我们常常使用算法的知识来解决问题。请根据你刚刚解决问题的思路，小组讨论得出你对算法的概念，以及算法应具备的特征。
一、算法的概念
算法
在生活和学习中，人们经常会运用到算法（algorithm）知识，只是很少意识到。从广义上讲，算法是为解决一类特定问题而采取的确定的、有限的步骤。它描述出某类问题求解的方法和过程，在整个问题解决过程中起着重要的作用。在计算机领域，算法作为一个精心设计的运算序列，描述了计算机如何将输入转化为输出的过程。
一、算法的概念
大家说一说生活中会用到哪些算法知识？
算法其实是对解决问题办法的抽象
概念：从广义上讲，算法是为解决一类特定问题而采取的确定的、有限的步骤。
在计算机领域，算法作为一个精心设计的运算序列，描述了计算机如何将输入转化为输出的过程。
一、算法的概念
有输入
有输出
确定性
有穷性
并不是所有解决问题的步骤都是算法，算法一般具有以下特性：
二、算法的特征
可行性
二、算法的特征
算法
特征
一个算法可以有一个或多个输出，以反映对输入数据加工后的结果。
算法的有穷性指算法必须能在执行有限个步骤之后终止，也就是算法步骤不能是无限的。
算法中的每一步操作都是可以执行的，或者都可以分解成计算机可执行的基本操作。
算法的每个步骤都具有确定的含义，没有歧义。模糊不清、模棱两可或带有二义性的描述都会影响算法的确定性。
有输入
有输出
有穷性
可行性
确定性
一个算法一般要求有0个或多个输入，以描述运算对象的初始情况。
三、算法的描述
同学们刚刚是如何记录或者描述解决问题的方法呢？
描述算法就是将解决问题的步骤，用一种可理解的形式表示出来。常用的描述算法的方法有自然语言、流程图和伪代码等。
如何描述算法？
语言？图像？
思考：如何将“15秒”倒计时的算法描述出来？
三、算法的描述
用自然语言描述算法
自然语言指人们日常所用的语言。用自然语言描述算法就是使用人们能读懂的简短语句对算法的步骤进行描述。其中，“倒计时15秒"算法可用自然语言描述为：
步骤1：将计数器设为15；
步骤2：如果显示的值大于或等于1，执行步骤3，否则倒计时结束；步骤3：输出显示屏信息，并保持显示1s，然后清除显示；
步骤4：将显示屏的值减1，跳转至步骤2.
用自然语言描述算法易于理解，它既可以描述生活中的算法，也可以描述在计算机中执行的算法。但是，自然语言的描述方法存在容易产生二义性的缺点，有可能干扰后续的编程实现。
三、算法的描述
用流程图描述算法
流程图是一种常用的表示算法的图形化工具。用流程图描述的算法直观易读，问题解决的步骤清晰简洁，算法结构表达明确，很适合初学算法的人员使用。流程图中常用的符号和功能如下：
开始/结束框
表示算法的开始或结束
输入/输出框
表示输入或输出数据
处理框
框中指出要处理的内容
判断框
表示条件判断及产生分支的情况
流程线
用于控制流程方向
连接点
连接因页面写不下而断开的流程线
三、算法的描述
循环结构
选择结构
顺序结构
顺序结构
每一个步骤按先后次序被执行，即执行处理A，然后执行处理B。
选择结构
根据条件的成立与否，选择执行不同的分支处理，当条件成立时用Tnue表示执行处理A；当条件不成立时用False表示，执行处理B。
循环结构
当条件成立时，反复执行处理A，一旦条件不成立就立即结束循环。
三种控制结构：
算法有顺序结构、选择结构和循环结构三种基本控制结构，可用流程图描述，如
三、算法的描述
在实际问题解决中，经常会综合使用这三种结构。例如，“倒计时15s”的算法可用如下的流程图描述。
思考：一个算法的流程图一定是相同的吗？
三、算法的描述
用伪代码描述算法
用伪代码描述算法就是采用一种类似于程序设计语言的代码来表示算法。伪代码没有固定的、严格的语法规则，只要定义合理，没有矛盾即可。例如，“倒计时15s"的算法用伪代码可以描述为：
t → 15
while t>=1
output t
sleep 1s
clear
t =t-1
end while
用伪代码描述算法回避了程序设计语言严格的书写格式，保持了语言叙述准确、无二义性的优点，结构性强，比较容易书写和理解。
第三部分
旧知回顾
新知学习
课堂巩固
拓展思考
巩固新知
注意：算法描述了问题求解的具体步骤，决定着问题解决的过程。解决同一问题可能会有不同的算法，不同算法求解的过程或有不同。
练一练（一）：请用你喜欢的方式描述小明乘电梯到达教室的算法
自然语言
流程图
伪代码
巩固新知
小试身手（二）：如果让计算机判断11是否为质数，如何设计算法步骤？
第一步：11除以2是否有余数？
第二步：11除以3是否有余数？
第n步：11除以n+1是否有余数？
第九步：11除以10是否有余数？
第十步：若以上均有余数则为质数，否则为合数。
请你用另外两种方法描述该算法

巩固新知
挑战困难（三）：某城市公交车票价2元，乘客可以刷卡乘车。刷卡时，若公交卡余额不足2元，提示“请投币”；若余额大于或等于2元但小于10元，则提示“余额即将不足”；若余额大于或等于10元，提示“欢迎乘车”。请用流程图描述该功能实现的算法。
Expand the thinking
旧知回顾
新知学习
课堂巩固
拓展思考
第四部分
Writing
Finding
Signal
逻辑思维和计算思维
中学生了解算法的基本设计方法，可以深入理解身边数字化工具的特征，能够利用算法思想解决实际问题，提高学习和生活效率，更好地融入信息社会。
一、为什么学习算法
冒泡排序
快速排序
二、两种算法的比较
VS
冒泡排序
快速排序
二、两种算法的比较
VS
冒泡排序
快速排序
二、两种算法的比较
VS
可以看出，解决排序问题，“快速”排序算法比“冒泡”排序算法快很多。解决同一个问题会有多种方法，人们往往需要考虑算法的“时间复杂度”和“空间复杂度”，并根据需求设计合适的算法，从而提高效率。学习算法知识，了解算法的基本设计方法，可以深入理解身边数字化工具的特征，能够利用算法思想解决实际问题，提高学习和生活效率，更好地融入信息社会。
算法
贪心算法
分支界限法
回溯法
空间复杂度
穷举法
动态规划法
递推法
递归法
时间复杂度
分治法
三、算法风暴
法
算
The concept and description of the algorithm
2.2算法的概念及其描述
请完成学案课后作业，同学们再见！
结 束！