资源简介

第 2 章 算法与程序实现
2.2 算法的概念及描述
教学设计
教学背景
信息科技是现代科学技术领域的重要部分，主要研究以数字形式表达的信息及其应用中的科学原理、思维方法、处理过程和工程实现。当代高速发展的信息科技对全球经济、社会和文化发展起着越来越重要的作用。
义务教育信息科技课程具有基础性、实践性和综合性，为高中阶段信息技术课程的学习奠定基础。信息科技课程旨在培养科学精神和科技伦理，提升自主可控意识，培育社会主义核心价值观，树立总体国家安全观，提升数字素养与技能。
教材分析
本节课的教学内容选自人教/地图出版社第 2 章 算法与程序实现　2.2 算法的概念及描述，信息技术的发展与普及为我们创造了一个全新的数字化生活环境。它们在给我们带来生活便利的同时，也在逐渐地改变着我们的生活方式。
2017 年 10 月的一天，在杭州市中心路段开展了一场救护车施救演练。在全程近 7 km 的路段中，救护车获准优先通行 21 次，平均行驶速度达36 km/h，相较于该路段常规通行时间，省时近 900 s。优先通行“抢”出的这十几分钟，可能就是挽回病患生命的“黄金”时间。在这个现实版的生死时速演练案例中，批准救护车优先通行的正是杭州“城市大脑”工程的“交通模块”。截至 2018 年初，杭州的“城市大脑”已接管了市区内的主要路口信号灯，通过各类数据感知交通态势，进而优化信号灯配时，使车辆通行速度提升近 15 %。这就是通过算法与程序设计对大数据进行综合应用的奇妙之处。
算法与程序浸润在我们生活的各个方面。计算机与移动终端已成为生活中不可或缺的工具，它们之所以能够帮助人们处理各种复杂的事情，主要借助于其中功能各异的程序。
在本章的学习中，我们将通过“编程控灯利出行”项目活动，学习如何利用编程的方式实现算法并解决问题，从而发展计算思维，掌握利用计算思维解决问的方法与策略。
学情分析
此节课针对的对象是高一年级的学生，学生对信息技术的关键技术以及信息技术对生活与学习的影响有一定的了解，但对所学内容只是体验性和经验性的认识。依据解决问题的需要，设计和描述简单算法;利用程序设计语言实现简单算法，解决实际问题。
教学目标
1.描述算法的特征，理解算法在问题解决中的作用。
2.选用恰当的描述方法和控制结构表示简单算法，增强用算法解决问题的意识。
教学重点与难点
理解算法的三种基本控制结构,能够选用恰当的描述方法和控制结构表示简单算法。
教学方法与教学手段
案例分析法、讲授法、任务驱动法。
教学过程
问题导入
提出问题，引发思考：
利用“牧羊人过河”游戏吸引学生注意力，引发学生的兴趣，激发学生的思考能力。
体验探索
规划乘车路线
小明同学所在城市的地铁线路局部图，如图 2.2.1 （参见教材P47）所示。他计划从 A 站出发去 B 站附近的图书馆学习。假设地铁各线路每两站间行车用时相等，记为t 1 ；换乘地铁的用时也都相等，记为t 2 。
思考：
1. 列举出由 A 站出发到达 B 站的所有换乘次数最少的乘车路线。
2. 如果小明同学希望尽快到达 B 站，试为他推荐一条最佳乘车路线，并说明理由。
认识算法
在生活和学习中，人们经常会运用到算法（algorithm）知识，只是很少意识到。从广义上讲，算法是为解决一类特定问题而采取的确定的、有限的步骤。它描述出某类问题求解的方法和过程，在整个问题解决过程中起着重要的作用。例如，表 2.2.1 所示的求两个正整数最大公约数的问题，应用的是我国古代《九章算术》中记载的“更相减损术”，其方法为“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
表 2.2.1 用“更相减损术”求两个正整数的最大公约数
两种情形 步骤
“不可半者”（如 153 和 119） 直接辗转相减，直至减数和差相等： ① 153-119=34 ② 119-34=85 ③ 85-34=51 ④ 51-34=17 ⑤ 34-17=17 　　所以，153 与 119 的最大公约数为 17
“可半者”（如 24 和 16） 第一步，先将 24 和 16 用 2 反复约简，直至不都是偶数，约数最后为 8（用 2 约简了三次） 第二步，分别将两个约简后的数辗转相减，直至减数和差相等： ① 3-2=1 ② 2-1=1 第三步，求差和约数的乘积：1×8=8 所以，24 与 16 的最大公约数为 8
在计算机领域，算法作为一个精心设计的运算序列，描述了计算机如何将输入转化为输出的过程。
算法一般具有如下特征：
有输入。一个算法一般要求有 0 个或多个输入，以描述运算对象的初始情况。例如，在用“更相减损术”求最大公约数的过程中，输入的是两个正整数。
有输出。一个算法可以有一个或多个输出，以反映对输入数据加工后的结果。例如，用“更相减损术”求得的最大公约数就是该算法的输出。
有穷性。算法的有穷性指算法必须能在执行有限个步骤之后终止，也就是算法步骤不能是无限的。例如，在用“更相减损术”求最大公约数的过程中，要求重复辗转相减直至减数和差相等。实际上，对于任意给定的两个正整数，无论原始值有多大，这个过程的执行次数都是有穷的。
可行性。算法中的每一步操作都是可以执行的，或者都可以分解成计算机可执行的基本操作。
确定性。算法的每个步骤都具有确定的含义，没有歧义。模糊不清、模棱两可或带有二义性的描述都会影响算法的确定性。
阅读拓展
为什么要学习算法
我们在生活和学习中会经常遇到算法。例如，楼宇电梯通常按照一定的算法响应用户请求，合理停靠到相应的楼层；铁路网络订票系统按照一定的算法设置订票模式，高效服务用户。
智能时代，算法已经广泛应用于各领域。许多专家通过分析行业的运行规律，界定问题，有针对性地建立模型、设计算法，并应用信息技术实现模型，从而创造出新的产品，创生出新的产业。例如，通过设计算法，在网络环境下实现“互联网 + 单车”，催生出“共享单车”这个新产业，解决短距离出行不便问题。
中学生学习一些算法知识，了解算法的基本设计方法，可以深入理解身边数字化工具的特征，能够利用算法思想解决实际问题，提高学习和生活效率，更好地融入信息社会。
描述算法
描述算法就是将解决问题的步骤，用一种可理解的形式表示出来。常用的描述算法的方法有自然语言、流程图和伪代码等。
思考活动
描述“红灯变绿灯”问题的算法
完善本章第一节思考活动“红灯变绿灯”功能，在交通信号灯下方增加一个 15 s 的“倒计时器”，提示过往的行人和车辆。
思考：
如何将“倒计时 15 s”的算法描述出来？
用自然语言描述算法
自然语言指人们日常所用的语言。用自然语言描述算法就是使用人们能读懂的简短语句对算法的步骤进行描述。其中，“倒计时 15 s”算法可用自然语言描述为：
步骤 1 ：将计数器 t 设为 15 ；
步骤 2 ：如果 t 大于或等于 1，执行步骤 3，否则倒计时结束；
步骤 3 ：输出 t，并保持显示 1 s，然后清除显示；
步骤 4 ：将 t 的值减 1，跳转至步骤 2。
用自然语言描述算法易于理解，它既可以描述生活中的算法，也可以描述在计算机中执行的算法。但是，自然语言的描述方法存在容易产生二义性的缺点，有可能干扰后续的编程实现。
用流程图描述算法
流程图是一种常用的表示算法的图形化工具。用流程图描述的算法直观易读，问题解决的步骤清晰简洁，算法结构表达明确，很适合初学算法的人员使用。流程图中常用的符号及其功能如表 2.2.2 （参见教材P50）所示。
绘制流程图的方法很多，可以手工绘制流程图，也可以用软件制作，如使用文本编辑软件中的“流程图”对象绘制，或使用专门的流程图绘制软件，还可以到在线绘制流程图网站进行制作。
算法有顺序结构、选择结构和循环结构三种基本控制结构，可用流程图描述，如图 2.2.2 （参见教材P51）所示。
顺序结构。每一个步骤按先后次序被执行，即执行处理 A，然后执行处理 B，如图 2.2.2（a）（参见教材P51）所示。
选择结构，又称分支结构。根据条件的成立与否，选择执行不同的分支处理，如图 2.2.2（b）（参见教材P51）所示。当条件成立时（用 True 表示），执行处理 A ；当条件不成立时（用False 表示），执行处理 B。
循环结构。当条件成立时，反复执行处理 A，一旦条件不成立就立即结束循环，如图 2.2.2（c）（参见教材P51）所示。
在实际问题解决中，经常会综合使用这三种结构。例如，“倒计时 15 s”的算法可用图 2.2.3 （参见教材P51）所示的流程图描述。
用伪代码描述算法
用伪代码描述算法就是采用一种类似于程序设计语言的代码来表示算法。伪代码没有固定的、严格的语法规则，只要定义合理，没有矛盾即可。例如，“倒计时 15 s”的算法用伪代码可以描述为：
t ← 15
while t≥1
output t
sleep 1s
clear
t ← t-1
end while
用伪代码描述算法回避了程序设计语言严格的书写格式，保持了语言叙述准确、无二义性的优点，结构性强，比较容易书写和理解。
算法描述了问题求解的具体步骤，决定着问题解决的过程。解决同一问题可能会有不同的算法，不同算法求解的过程或有不同。例如，在“体验探索”的“规划乘车路线”过程中有多种解决方法，由于换乘的次数和乘坐的站点数不同，采用不同的方法乘车，总用时并不相同，但要想“尽快到达 B 站点”，其中用时最少的一组应该是该问题求解的最佳方法。
实践活动
找出质量较轻的零件
已知有 10 个一模一样的零件，其中 9 个零件的质量相同，只有 1 个质量略轻，不符合规格要求。现在有一台天平，请设计算法找出该零件。
1. 如果采用一一比较的方法，逐一称重对比，最多需要比较多少次才能找出这个质量较轻的零件？试着描述该算法，想一想还有哪些方法可以解决该问题？
2. 如果有n 个零件（n ＞ 10），要找出其中质量较轻的一个，以上方法是否仍然可用？试分析n=10 000 时，这些算法在问题解决效率上的不同。
阅读拓展
算法与数字生活
算法与数字生活息息相关，如使用机器人清理房间，通过智能运动手环进行科学健身，输入用户口令安全登录账户等，算法都在其中起着重要的作用。借助高效的算法和优化的程序，我们可以更加快捷方便地解决越来越多的问题，提高生活、工作和学习效率。
用数字化工具解决问题离不开程序的控制，而程序的核心是算法设计。
算法描述了解决问题的步骤，程序则是用某种程序设计语言将设计好的算法进行具体实现，从而实现自动化的问题求解。
例如，空调具有的定时关机功能，就可以通过倒计时算法来实现。在设定关机时间后，系统将进行倒数计数，当计数结束时就会发出关机指令，关闭空调。
再如，某城市公交车票价 2 元，乘客可以刷卡乘车。刷卡时，若公交卡余额不足 2 元，提示“请投币”；若余额大于或等于 2 元但小于 10 元，提示“余额即将不足”；若余额大于或等于 10 元，提示“欢迎乘车”。用流程图描述该功能实现的算法如图 2.2.4 （参见教材P53）所示。
项目实施
描述项目问题的算法设计
一、项目活动
结合“编程控灯利出行”项目，在完成“自助式人行过街红绿灯”的问题分析和功能分解之后，对各功能进行算法设计，并用流程图的方式描述出来。
二、项目检查
设计项目任务实现的算法，并用流程图描述出对应的算法
课后作业
练习提升
1. 小明早上从起床到出门上学需要洗漱（5 min）、烧水（10 min）、准备早餐（10min）、吃早餐（15 min）和听新闻（10 min），试帮他统筹安排各项事务，设计一个合理的算法步骤。
2. 某地有两种不同类型的出租车，其计费标准分别为：
● 甲车 3 km 起步，价格为 10 元，3 km 以上（含 3 km）为 2 元 / km ；
● 乙车 3 km 起步，价格为 8 元，3 km 以上（含 3 km）为 2.2 元 / km。
设计算法，在不同里程时给出最优资费的用车选择。选用一种算法描述方法对该算法进行描述。
3. 欧几里得算法又名辗转相除法，其算法可用图 2.2.5 （参见教材P54）所示的流程图描述（“%”为取模运算符，可返回除法的余数），认真阅读流程图，分析该算法实现的功能。
板书设计
第 2 章 算法与程序实现
2.2 算法的概念及描述
1.认识算法
2.描述算法
用自然语言描述算法
用流程图描述算法
用伪代码描述算法
普通高中教科书
信息技术　必 修 1　数据与计算
编著
人民教育出版衬课程教材研究所信息技术课程教材研究开发中心
中国地图出版社教材出版分社
总 主 编 ：祝智庭 樊 磊
副总主编 ：高淑印 郭 芳 李 锋
本册主编 ：李 锋 高淑印
编写人员 ：程建娜 刘姝弘 夏燕萍 王 岚 史弘文

展开更多......

收起↑