2.2 算法的概念及描述 课件 2022—2023学年人教_中图版 高中信息技术必修1（22张PPT）

(共22张PPT)
人教中图版普通高中教科书
第二章 算法与程序实现
2.1解决问题的一般过程和用计算机解决问题
2.2算法的概念及描述
2.3程序设计基本知识
2.4常见算法的程序实现
描述算法的特征，理解算法在问题解决中的作用
选用恰当的描述方法和控制结构表示简单算法，增强用算法解决问题的意识
学习目标
体验探索
规划乘车路线
小明同学所在城市的地铁线路局部图，如图所示。他计划从A站出发去B站附近的图书馆学习。假设地铁各线路每两站间行车用时相等，记为t1；换乘地铁的用时也都相等，记为t2。
体验探索
规划乘车路线
思考：
1.列举出由A站出发到达B站的所有换乘次数最少的乘车路线图。
2.如果小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线，并说明理由。
第1题：
换乘次数最少（只换乘1次）的乘车线路：A-E-B或A-J-B或A-Q-B或A-P-B
第2题：
最佳乘车路线，既需考虑换乘次数，还需考虑乘车时间，甚至有时还要根据需要考虑t1和t2的大小。这里最佳路线是A-J-B,总用时5t1+t2
算法的概念
枚举法/穷举法
大家用列举的办法解决了规划乘车路线的问题，如果可能性更多问题更复杂，怎么办？
思考活动：计算机如何解决实际问题？
计算机解决问题依靠的是程序，而程序的编写依赖于算法和计算机“语言”， 即首先将需要解决的问题分解为若干个明确的步骤（算法），然后在用计算机能够接受的“语言”准确的描述出来，这样计算机才能够解决问题。
算法的概念
思考活动：什么是算法
在学习和生活中我们常常使用算法的知识来解决问题。请根据你刚刚解决问题的思路，小组讨论得出你对算法的概念，以及算法应具备的特征。
广义上讲，算法是解决一个特定问题而采取的确定的、有限的步骤。
当你想要从遵义去上海迪士尼旅游，你会如何规划行程呢？
算法的概念
① 网上购买迪士尼门票；
② 根据日期，购买火车票或者飞机票；
③ 根据行程及日期安排，预订住宿酒店；
④ 带好各种票据，准备好行李，按时乘车；
⑤ 到达上海，乘坐出租车或公共交通车辆去往酒店入住，放行李；
⑥ 带好门票，按时到迪士尼游玩。
算法就是在解决特定问题时，采取的确定的、有限的步骤。
解决同一个问题的算法可能有多种。
其他方案
算法的特征
分析解决以下三个问题的方法，归纳算法的特征
算法的特征
判断抛物线 =5 2+4 ++6与 轴是否有交点。
计算△= × × ；
如果△大于等于0，执行步骤③，否则执行步骤④；
输出有交点，结束；
输出无交点，结束。
算法的特征
分析项目 ①抛物线 ②分段函数 ③绝对值
执行的步骤个数 4
每一步是否明确可执行 是
是否有输入 无
是否有输出 有
算法的特征
分析项目 ①抛物线 ②分段函数 ③绝对值
执行的步骤个数 4 5 4
每一步是否明确可执行 是 是 是
是否有输入 无 有 有
是否有输出 有 有 有
算法的特征
算法的特征
有输入
一个算法通常要求有0个或多个输入。
有输出
一个算法可以有一个或多个输出。
有穷性
算法必须能在有限个步骤之后终止。
可行性
算法中的每一步都是可以执行的。
确定性
算法的每个步骤都具有确定的含义，没有歧义。
算法描述的方法
描述算法就是将解决问题的步骤，用一种可理解的形式表示出来。常用的描述算法的方法有自然语言、流程图和伪代码等。
思考活动：描述“红灯变绿灯”问题的算法
完善本章第一节思考活动“红灯变绿灯”功能，在交通信号灯下增加一个15s的“倒计时器”，提示过往的行人和车辆。
思考：如何将“倒计时15s”的算法描述出来
算法描述的方法
用自然语言描述算法
用自然语言描述算法就是使用人们能读懂的简短语句对算法的步骤进行描述。其中“倒计时15s”算法可以用自然语言描述为：
步骤1：将计数器t（剩余秒数）设为15；
步骤2：如果t大于等于1，执行步骤③，否则倒计时结束；
步骤3：输出t，并保持显示1秒，然后清除显示；
步骤4：将t的值减1，跳转至步骤②。
易于理解
有歧义
算法描述的方法
用流程图描述算法
流程图是用图形表示算法的一种常用工具。用流程图描述的算法直观易读，问题解决的步骤清晰简洁，算法结构表达明确。
开始/结束框
输入/输出框
处理框
判断框
流程线
连接点
表示算法的开始或结束
表示输入或输出数据
框中指出要处理的内容，此框有一个入口和一个出口
用于表示条件判断及产生分支的情况，判断框有四个顶点，通常上面的顶点表示入口
用于控制流程方向
用于连接因页面写不下而断开的流程线
算法描述的方法
算法有顺序结构、选择结构和循环结构三种基本控制结构，可用流程图描述，如：
顺序结构
每一个步骤按先后次序被执行，即执行处理A，然后执行处理B。
选择结构
根据条件的成立与否，选择执行不同的分支处理，当条件成立时用Tnue表示执行处理A；当条件不成立时用False表示，执行处理B。
循环结构
当条件成立时，反复执行处理A，一旦条件不成立就立即结束循环。
算法描述的方法
“倒计时15s”算法流程图
结束
t ← 15
t ≥ 1
输出t
t ← t-1
True
False
保持显示1秒
清除显示
开始
算法描述的方法
用伪代码描述算法
用伪代码描述算法就是采用一种类似于程序设计语言的代码来表示算法。伪代码没有固定的、严格的语法规则，只要定义合理，没有矛盾即可。
“倒计时15s"的算法用伪代码可以描述为：
t → 15
while t>=1
output t
sleep 1s
clear
t =t-1
end while
优点：回避了程序设计语言严格的书写格式，叙述准确，无二义性，结构性强。
缺点：需要具备一定的程序设计语言基础，不利于初学者使用。
算法的效率
实践活动：找出质量较轻的零件
已知有10个一模一样的零件，其中9个零件的质量相同，只有一个质量略轻，不符合规格要求。现在有一台天平，请设计算法找出该零件。
1.如果采用一一比较的方法，逐一称重对比，最多需要比较多少次才能找出这个质量较轻的零件？试着描述该算法，想一想还有哪些方法可以解决该问题？
2.如果有n个零件（n>10），要找出其中质量较轻的一个，以上方法是否仍然可用？试分析n=10000时，这些算法在问题解决效率上的不同。
算法的效率
1.如果采用一一比较的方法，逐一称重对比，最多需要比较多少次才能找出这个质量较轻的零件？试着描述该算法，想一想还有哪些方法可以解决该问题？
一一比较：1-5次
二分法：2-3次
算法的效率
2.如果有n个零件（n>10），要找出其中质量较轻的一个，以上方法是否仍然可用？试分析n=10000时，这些算法在问题解决效率上的不同。
一一比较：1~5000次
二分法：5~13次（效率更高）
解决问题时，可根据问题规模，选择合适算法
课程小结