资源简介

(共35张PPT)
第2章 算法与问题解决
浙教版（2019版） 信息技术（高中）
必修1 数据与计算
2.1 算法的概念及描述
·广义地讲，算法指的是解决问题或完成任务的一系列步骤。
·古代的算法主要指的是“算术”，即数值的算术运算。
古籍——《盘珠算法》
【2.1.1】算法自古就有
田忌赛马中的博弈算法
·在计算机科学领域内，算法是指用计算机解决问题的步骤，是为了解决问题而需要让计算机有序执行的、无歧义的、有限步骤的 集合。
【2.1.1】算法的定义
你能根据步骤推出运算结果吗？
√ 有穷性
一个算法的处理步骤必须是有限的。
√ 确定性
算法中对于每个步骤的执行描述必须是明确的。
√ 可行性
算法中的每一步操作与要求都应该是算法执行者可以实施的，同时在现实环境中能做到且能在有限的时间内完成。
√ 有0个或多个输入
初始数据可以从外界输入，也可包含在算法中，所谓0个输入是指本身给出了初始条件。
√ 有1个或多个输出
算法必须有问题求解的结果，包含至少一个输出。
【2.1.1】算法的特征
【无限循环】
该流程图违反了算法的什么特征？
1、在设计一个排序算法时，给出的指令是
“将数组中的元素按照一定顺序排列，相邻元素的差值尽可能小”。
“相邻元素的差值尽可能小” 这一表述是模糊的。对于具体如何实现 “尽可能小” 没有明确规定。
不同的人可能会有不同的理解和实现方式，比如，有人可能会优先考虑整体差值的平均值最小，而有人可能会先让前几个元素的差值最小，这样就会导致算法的结果不唯一，违反了算法的确定性。
2、在路径规划算法中，指令为 “找到一条从起点到终点的较优路径，尽量避开拥堵区域”。
“较优路径” 和 “尽量避开” 都是模糊的表达。
“尽量避开” 也没有明确规定避开的程度和判断拥堵的具体标准，不同的算法实现可能会得出完全不同的路径规划结果，无法保证算法的确定性。
该语句违反了算法的什么特征？
为防止用户账户被盗，在用户登录账户时，有些信息系统会限制用户尝试输入密码的次数(如图2.1.2),一旦超出限定的次数，系統就会禁止输入并要求进行注册账户验证。下面为某系统验证用户输入密码正确与否的算法：
①密码输入错误次数初始化为零。
②接受用户输入的密码。
③将用户输入的密码与原来设置的密码比较，若相同则转 ，否则转④。
④密码输入错误次数增加1。
⑤若密码输入错误次数少于5，输出信息“密码错误，请再次输入密码！ ”，然后转⑥；否则，输出信息“密码输入错误已达5次，请通过注册邮箱找回密码”，然后转 。
⑥接受用户输入的密码，然后转③。
⑦密码正确，进入系统。
⑧密码验证算法结束。
问题与讨论1：
1、该算法采用了什么形式来描述？
2、结合上述算法，谈谈算法的特征在其中的具体体现。
3、若顺序打乱，程序是否还能够按照逻辑运行？这体现了算法的什么特征？具有这种特征的控制结构称为____结构？
很多设备的“自动”功能，都是内部算法控制的结果。
比如，在夏天把空调温度设定在26℃，每当空调内部的温度传感器测得室内温度小于或等于26℃时，算法就会“告诉”空调已经到达目标温度，可以暂停工作，空调就会“自动”暂时关闭压缩机的运行。这样，既确保了室内温度，又实现了节能环保。
立式空调
拓展链接：
明确参与运算的初始数据、运算时产生的中间数据以及代表问题解决的结果数据。
明确每一步的运算是什么、对哪些数据进行运算等。
根据数据或运算结果的特点进行不同的处理。
数据
运算
控制转移
【2.1.3】△算法的要素
【2.1.4】算法的描述
题目1：停车场车位探测器算法
情境：某智能停车场需要在每个车位安装指示灯，实时显示车位是否空闲。
请设计一个算法，根据传感器的输入信号（1表示空车位，0表示非空车位）控制指示灯颜色，并通知区域控制器；
实现无车时，绿灯亮，显示“空车位” 或 有车时，红灯亮，显示“非空车位”。
任务要求
自然语言描述：
用“输入 - 处理 - 输出”的格式说明如何处理传感器数据。
所谓处理，指的是不同的输入值对应的情况；
输出即将这个情况导致的结果输出。
参考格式：
首先，输入________________。
如果信号的值为____，则亮__灯，显示“________”。
如果信号的值为____，则亮__灯，显示“________”。
【2.1.4】①用自然语言描述算法
情境：智能空调需依据室内温度传感器信号（设 25℃及以下时传感器输出 1，高于 25℃时输出 0 ），自动调节制冷状态并向手机 APP 反馈。
实现室内温度适宜（对应传感器信号 1 ）时，空调处于通风模式，显示 “室内凉爽，通风运行”;室内温度较高（对应传感器信号 0 ）时，空调开启制冷模式，设定温度 25℃，显示 “室内偏热，制冷运行”。
任务要求
自然语言描述：
用“输入 - 处理 - 输出”的格式说明如何处理传感器数据。
所谓处理，指的是不同的输入值对应的情况；
输出即将这个情况导致的结果输出。
试着用自然语言描述该算法
无限循环
【2.1.4】②用流程图描述算法
输入传感器信号（1或0）。
如果信号是1：
亮绿灯，显示“空车位”。
否则：
亮红灯，显示“非空车位”。
试着用流程图描述该算法
伪代码指的是一种比较直观简洁的、符号接近计算机程序代码的算法描述方式，其风格很像计算机程序设计语言，但又不是真正的可以被计算机理解的代码。
伪代码的表示方法没有统一、严格的规定，只要定义合理、表达正确即可。
（1）条件判断语句
格式1：
If 条件 then
（语句序列1）
Else
（语句序列2）
格式2：
If 条件 then
（语句序列1）
（2）循环语句
格式：
while 条件
（循环体）
【2.1.4】③用伪代码描述算法
描述方式 优点 缺点
自然语言 不需要专门训练，通俗易懂 存在歧义性、语句长，循环和分支较多时难以清晰表示，不便翻译成计算机程序设计语言
流程图 描述清晰简洁，容易表达选择结构，利于不同环境的程序设计 无法被计算机直接接受进行操作
伪代码 易于理解，便于向计算机程序设计语言过渡 种类繁多，语句不容易规范
【2.1.4】三种算法描述方式的优劣
Python实现
C++实现
【2.1.4】④用计算机程序设计语言描述算法
计算机程序设计语言经历了“机器语言一汇编语言一高级语言”的发展历程。
机器语言中的指令由“0”“1”二进制码组成，机器执行效率高但可读性、维护性差。
为了提升编程的效率，科学家用特定的符号（助记符）来表示各个机器指令，发明了汇编语言。比如ARM汇编语言，能够与高级语言相互补充，高级语言反过来依赖于汇编语言实现底层操作。
科学家后来又发明了高级语言，用接近人类日常用语的符号来表示各类指令。常见的高级语言有Basic、C、C++、Java、Python、Ruby等。
【2.1.4】计算机程序设计语言（拓展链接）
1. 用自然语言描述“高一新生报到流程”对应的算法。
2.用智能电饭煲烧饭时，在微处理器的控制下，当饭烧熟时，智能电饭煲会自动停止高热烧饭，转为低热保温。这是因为锅底的温度传感器每隔一定时间(比如200毫秒)会将温度数据传送给微处理器，一旦发现温度达到103℃(此时锅中水被蒸发完)，微处理器就会控制继电器释放触点，让电饭煲停止烧饭，转入低热保温模式。
图中所示的流程图描述了某个时刻智能电饭煲根据输入的温度数据进行判断、处理的算法，则在流程图中①、②标记处应填入的内容分别为①____________、②____________(选填“变为低热保温”或“继续高热烧饭”)。
问题与讨论2：
第二课时
算法的控制结构有三种，分别是：
顺序结构、分支结构和循环结构 ；
任何复杂的系统都可以由这三种结构组合来实现。
【2.1.6】算法的控制结构
类似地，无论内容怎样复杂、功能如何强大的算法，也都由基本的结构组合而成，这些基本的结构称为算法的控制结构。
再复杂的积木作品，都是由最基本的积木块（不妨称为基本结构）通过各种组合构成的。
概念：
算法中各个步骤按照先后顺序依次执行的结构。
特点：
1、每个步骤按照算法中出现的顺序依次执行。
2、每个步骤一定会被执行一次，而且只执行一次。
第一个操作
第二个操作
第三个操作
【2.1.6】顺序结构
顺序结构算法的流程图
概念：
先进行条件判断，再根据判断结果分别执行不同处理的结构称为分支结构（也称选择结构）。
特点：
1、首先进行条件判断，根据条件满足与否来决定执行哪个分支。
2、在一个分支结构中，必定有一个分支被执行，其他的分支被忽略。
【2.1.6】分支结构
·分支结构可以分为单分支结构和双分支结构。
它们的区别在于：
·单分支结构，若条件为真，则执行相应语句，否则不执行该语句；
·双分支结构，若条件为真，则执行语句 1，否则执行语句 2。
【2.1.6】分支结构
用python打开 分支结构判断_流程图.py 文件
并结合分支结构的概念和特点，完成其中的题目
【2.1.6】分支结构的程序实现
【2.1.6】生活中的循环
循环条件满足？
循环体
是
否
①算法会先判断循环条件是否满足。
②若满足则进入循环，执行循环体，然后再次判断循环条件是否满足，若满足则再次进入循环，执行循环体，然后再次判断循环条件是否满足......
③直到某次循环条件不满足，退出循环。
死循环/无限循环 违背了算法的什么特征？
【2.1.6】循环结构
while 条件
循环体
【2.1.6】循环结构
空调是通过重复计算来实现对房间温度的控制。
重复计算的过程，可以用循环结构来表示，一次选择计算的过程就是它的循环体，空调重复计算的过程可以用该流程图表示：
第三课时
问题分析
抽象与建模
设计算法
描述算法
“四步骤”
【2.1.5】利用算法解决问题的四步骤（以下简称“四步骤”）
【2.1.5】用四步骤来表示欧几里得算法（辗转相除法）
材料已给出对猜数字游戏的抽象与建模，试着画出猜数字游戏的流程图
穷举算法也称枚举算法，指的是在求解过程中，先按照一定的顺序一一列所有可能的解，然后用条件判断列举出的可能解是否为正确解。穷举法一般适合解决解集为离散的且范围明确的问题。
“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买鸡百，问翁、母、雏各几何？”这是我国古代数学家在《算经》中提出的经典问题。同时，他还在书中给出了解决该问题的算法“鸡翁每增四，鸡母每减七，鸡雏每益三，即得＂。
百钱买百鸡
穷举算法
课后习题
基于“四步骤”；
用顺序、分支、循环结构组成流程图；
以描述 用枚举算法 解决百钱买百鸡问题 的过程。
习题答案：
顺序结构：按照流程依次执行的步骤，比如从 “开始” 之后，依次进行 “初始化变量 x=0,y=0” ，然后判断 “是否 x <= 20” 等，这一系列步骤是按顺序依次进行的，体现了顺序结构。
分支结构：图中的菱形判断框，如 “是否 x <= 20” “是否 y <= 33” “5 * x + 3 * y + z / 3 == 100 且 z % 3 == 0” ，根据判断结果的 “是” 或者 “否” 走向不同的流程分支，这属于分支结构。
循环结构：在 “是否 x <= 20” 判断中，当结果为 “是” 时，会不断循环判断 “是否 y <= 33” 等一系列操作，直到 “是否 x <= 20” 判断结果为 “否” 才跳出这部分循环，体现了循环结构。

展开更多......

收起↑