资源简介

第 2 章 算法与程序实现
2.4 常见算法的程序实现
教学设计
教学背景
信息科技是现代科学技术领域的重要部分，主要研究以数字形式表达的信息及其应用中的科学原理、思维方法、处理过程和工程实现。当代高速发展的信息科技对全球经济、社会和文化发展起着越来越重要的作用。
义务教育信息科技课程具有基础性、实践性和综合性，为高中阶段信息技术课程的学习奠定基础。信息科技课程旨在培养科学精神和科技伦理，提升自主可控意识，培育社会主义核心价值观，树立总体国家安全观，提升数字素养与技能。
教材分析
本节课的教学内容选自人教/地图出版社第 2 章 算法与程序实现　2.4 常见算法的程序实现，信息技术的发展与普及为我们创造了一个全新的数字化生活环境。它们在给我们带来生活便利的同时，也在逐渐地改变着我们的生活方式。
2017 年 10 月的一天，在杭州市中心路段开展了一场救护车施救演练。在全程近 7 km 的路段中，救护车获准优先通行 21 次，平均行驶速度达36 km/h，相较于该路段常规通行时间，省时近 900 s。优先通行“抢”出的这十几分钟，可能就是挽回病患生命的“黄金”时间。在这个现实版的生死时速演练案例中，批准救护车优先通行的正是杭州“城市大脑”工程的“交通模块”。截至 2018 年初，杭州的“城市大脑”已接管了市区内的主要路口信号灯，通过各类数据感知交通态势，进而优化信号灯配时，使车辆通行速度提升近 15 %。这就是通过算法与程序设计对大数据进行综合应用的奇妙之处。
算法与程序浸润在我们生活的各个方面。计算机与移动终端已成为生活中不可或缺的工具，它们之所以能够帮助人们处理各种复杂的事情，主要借助于其中功能各异的程序。
在本章的学习中，我们将通过“编程控灯利出行”项目活动，学习如何利用编程的方式实现算法并解决问题，从而发展计算思维，掌握利用计算思维解决问的方法与策略。
学情分析
此节课针对的对象是高一年级的学生，学生对信息技术的关键技术以及信息技术对生活与学习的影响有一定的了解，但对所学内容只是体验性和经验性的认识。依据解决问题的需要，设计和描述简单算法;利用程序设计语言实现简单算法，解决实际问题。
教学目标
1.理解解析算法和枚举算法，根据需要选用这两种算法，编程实现简单问题求解。
2.认识问题解决中不同算法的效率，完成项目程序的调试与运行。
教学重点与难点
理解解枚举法的含义与基本思想，难免通过编号实现算法。
教学方法与教学手段
案例分析法、讲授法、任务驱动法。
教学过程
问题导入
提出问题，引发思考：
枚举法是依据问题的己知条件，确定答案的大致范围，在此范围内列举出它所有可能情况的方法。在列举过程中:
1.不能遗漏任何一个正确解;
2.通过逐一判断，验证哪些情况满足问题的条件，从而得出问题的答案。
体验探索
绿灯时长的最优设置
通常，行人步行速度约为 4.4 km/h，观察到信号灯变化后的反应时间约为 2 s。要保证过街行人能走过长为 20 m 的人行横道（图 2.4.1）（参见教材P70），人行过街绿灯时长至少需要设置为多少？
思考：
1. 写出求解绿灯最短时长的计算公式。
2. 结合实际道路情况，思考在设置人行过街绿灯时长时需要考虑哪些因素，试着给出绿灯时长的最优设置模型。
基于解析算法的问题解决
解析算法指通过找出解决问题的前提条件与结果之间关系的表达式，并计算表达式来实现问题的求解。
许多问题可以通过分析，抽象成数学模型，借助解析式，用已知条件为变量赋值进行求解。例如，在“体验探索”中求解行人过马路最短绿灯时长时，可以应用行程问题相关公式，先计算行人过马路的时间
，然后建立数学模型 ，得到行人过街绿灯最短时长公式 ，最后只要将已知条件代入公式即可完成该问题求解。
例 1：自由落体运动问题。
问题：从离地 500 m 的高处自由落下一个小球，求从开始落下的时刻起，小球在最后1 s 内的位移（重力加速度 g 以 9.8 m/s 2 计）。
（1）分析问题
已知条件：小球离地高度 500 m，重力加速度 g 为 9.8 m/s 2 ；
求解目标：小球在下落最后 1 s 内的位移；
已知与未知的关系：可用自由落体运动位移与时间关系的公式，求解出下落时间 t，以及最后 1 s 内小球的位移。
（2）设计算法
在该问题中，要计算最后1s内小球的位移，首先要求出小球的落地时间t，由h= 1／2 gｒ2 可以得出落地时间 ；然后计算前 (t-1) s 小球下落的高度 hx ；最后求出总高度 h（500 m）与 hx 的差 hh，即为最后 1 s 内小球的位移。
（3）编程实现与调试
（4）保存文件，调试运行程序
实践活动
编写程序研究某山地的气温分布
某地区为了开发山区农业，需要了解山地的气候变化。现已知该地山区海拔每升高 100 m，气温下降约 0.5 °C，山地最高海拔为 1 500 m，山脚下的年平均气温为 22 °C（假设山脚海拔为 0 m）。
1. 依据气温随海拔升高而变化的规律，写出计算该山地不同海拔高度的气温的解析式，并编程实现。
2. 某种植物适宜生长在气温为 18 ～ 20 °C的山区，如果要分析这种植物应被种植在该山地多高的地区为宜，需要如何修改算法？试编程实现。
编程解决问题时，要善于综合运用物理、数学、化学等学科的知识和方法来分析问题，寻找问题中各要素之间的关系，用形式化的符号和公式表达要素之间的关系，得出解决问题所需的表达式。例如，我们用自由落体运动的相关公式来求解小球位移的问题，用一元二次方程求根公式求解方程等。生活中许多问题也可以用解析算法解决，例如，通过银行贷款买房后每月还贷金额的计算、打折商品价格的计算及求体重指数等。
利用“割圆术”求 π 的近似值“割圆术”是求圆周率的一种算法。我国古代数学家刘徽发现当圆内接正多边形的边数无限增加时，其面积可无限逼近圆面积，即所谓“割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体，而无所失矣”。同时，这些圆内接正多边形每边外有一个余径（线段 AB），如图2.4.3 （参见教材P72）所示。用边长乘余径，加到正多边形的面积上，则大于圆的面积，这样就可以得到圆面积的上限和下限。于是，刘徽采用了“以直代曲、无限趋近、内外夹逼”的思想，创立了“割圆术”。
“割圆术”从理论上能够把 π 的值计算到任意精度。刘徽用这种方法首先从圆内接正六边形开始割圆，算到正 192 边形的面积，得到 π 值为 3.14，又算到正 3 072 边形的面积，得到 π 值为 3.141 6。南北朝数学家祖冲之继承并发展了刘徽的“割圆术”，求得 π 的范围为 3.141 592 6 ＜ π ＜ 3.141 592 7，这个值在世界上处于领先地位超过 1 000 年。
基于枚举算法的问题解决
枚举法是依据问题的已知条件，确定答案的大致范围，在此范围内列举出它所有可能情况的方法。在列举过程中，不能遗漏任何一个正确解，通过逐一判断，验证哪些情况满足问题的条件，从而得到问题的答案。
在枚举算法的编程中，首先，要确定枚举对象和枚举范围，验证问题成立的条件；然后，借助循环语句和条件语句进行相应的程序设计，实现问题解决。
例 2：票据中模糊数字推断问题。
问题：一张票据上有一个由 4 位数字组成的编号，甲说数字编号的前两位数字相同，但都不是零；乙说数字编号的后两位数字是相同的，但与前两位不同；丙说数字编号是一个整数的二次方。试根据以上线索推断出编号。
（1）分析问题
已知条件：假设4位数字的编号是AABB，其中 A ≠0，A≠B，且AABB 是一个整数的二次方；求解目标：票据中的数字；
已知与未知的关系：要求解的 4 位数字的编号必须同时满足所有的已知条件。
（2）设计算法
根据问题分析，只要一一列举出 4 位数字 AABB 中 A 与 B 的所有可能组合，保证 A ≠ B且 A ≠ 0，再验证二次方问题，就可以得到问题的解。因此，该问题可使用枚举算法求解完成，其算法的流程图如图 2.4.4 （参见教材P74）所示。
（3）编程实现与调试
（4）保存文件，调试运行程序
枚举算法在生活中有着比较广泛的应用场景，适合解决求解的答案数量有限，并且可能的答案是能按照某种规则列举出来的问题。例如，用枚举法解决一些数学问题（“韩信点兵”“鸡兔同笼”等）、益智游戏和逻辑推理等。
枚举算法需要逐一验证所有可能的情况，运算量比较大，解决问题的效率不够高。因此，在应用枚举法求解问题时，需要考虑优化算法，选择恰当的枚举对象，尽量分析出问题中的隐含条件，缩小枚举范围，以提高解决问题的效率。
寻找 1 000 以内的所有素数
编程求解 1 000 以内的所有素数。素数是在大于 1 的自然数中，除了 1和它本身以外不再有其他因数的数，如 2，3，5，7，11，...
1. 分析该问题的枚举范围和验证条件。
枚举范围：＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ 。
验证条件：＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ 。
2. 用流程图描述问题求解的算法，并编程实现。
3. 教学资源平台中提供了本题的两种不同的算法方案（算法 A 和算法B），任选一种与自己设计的算法进行对比分析，完成表 2.4.1。思考其中哪种算法能更高效地解决问题，为什么？
表 2.4.1 两种方案的算法比较分析
算法方案 枚举对象 枚举范围 验证条件
自己的算法
对比的算法（□算法 A □算法 B）
算法是人们在解决问题中积累的一种“智慧”。通过大量实践，现在已经总结出许多行之有效的算法，除了本节中用到的解析算法和枚举算法外，还有许多经典算法，如排序、查找和分治等．
阅读拓展
递归方法
递归是用于设计算法的一种思想方法，也是计算机科学中一个十分重要的概念。它通常是把一个大型复杂的问题层层转化为一个与原问题相似的、规模较小的问题来求解，通过构建递归关系式，将解决小问题作为解决大问题的入口，由此，大问题也就“迎刃而解”。
具体来讲，一个问题能够适用递归方法解决，必须符合两个条件：
一个规模较大的问题可以分解为若干性质相同的规模较小的问题，这些规模较小的问题仍然可以进一步分解，分解出的新问题的解法和原问题的解法相同，只是处理对象的规模不同。
必须有一个明确的结束递归的条件，不得无限递归。
递归不仅仅是设计算法的一种思想方法，也是一种简化问题的思维方式。
算法与程序实现的综合应用
算法设计及其程序实现是用计算机解决问题的核心过程。在具体的问题解决中，需要综合应用不同的算法思想并编程实现。当程序运行结果不能完全满足问题求解要求时，还要对算法和程序进行完善和优化。
例 3：查找文稿中高频词的问题。
问题：学校开展经典诵读活动，小明在阅读《三国演义》时，为了分析小说的写作特色，想把小说中出现次数最多的 20 个词查找出来。想一想小明如何通过编写程序来实现呢？
（1）分析问题
要解决《三国演义》小说中高频词的查找问题，使用手工方式逐一查找统计，不仅费时费力，而且任务完成难度也非常大。此时，我们可以对问题进行抽象处理，确定出能用计算机解决的任务，将其转化为可计算问题，通过编程实现问题的高效求解。
已知条件：文本文件《三国演义》；
求解目标：《三国演义》中的高频词（以出现次数最多的 20 个词为例）；
已知与未知的关系：统计《三国演义》文本中词频，找出出现次数最多的 20 个词。
（2）设计算法
在查找文稿中高频词的问题求解中，除了要完成读取文件和显示输出内容，还要重点实现分词、词频统计和排序等功能。因此，该问题可以分解为如图 2.4.5 （参见教材P77）所示的 5 个功能。
1）读取文件
提前准备好《三国演义》文本文件，打开并读取文件内容。
2）中文分词
由于中文文本是由连续的字序列构成，没有明显的词语界限，因此分词处理的算法比较复杂。这里，我们可以直接使用现有的分词算法，如在 Python 语言中利用 jieba 分词功能，对读取到的《三国演义》字符串进行分词处理，如图 2.4.6 （参见教材P77） 所示，将汉字字符序列切分成一个个单独的词，组合成一个“词汇表”，即词的序列。
3）词频统计
词频统计的过程主要应用了枚举算法，对于“词汇表”中的每一个词，依次计算出各自的出现次数，生成一个包含词和次数的“统计表”。需要注意的是，在算法设计时还要考虑问题求解的“高频词”应是具有明确指向意义的词语，不包括单个字的词。因此，《三国演义》小说中实现词频统计功能的算法流程图表示如图 2.4.7 （参见教材P77）所示。
4）词频排序
要找到出现次数最多的 20 个词，需要对统计出来的词语按次数从大到小进行排序。
排序的算法有很多，我们可以自己设计排序算法，也可以调用已有的排序算法功能，如在 Python 语言中直接调用内置的排序函数快速实现序列排序。
5）显示输出降序排序后，序列中的前 20 个元素可认为是《三国演义》小说中出现次数最多的 20个词。此时，只需要显示输出序列中这前 20 个元素的值（包括词和对应次数）即可。
（3）编程实现与调试
（4）保存文件，调试运行程序
为了更有效地查找、修改程序中存在的错误，需要仔细阅读和分析程序语句，掌握必要的调试方法。
较简单的调试方法是通过函数 print( ) 直接输出程序执行过程中的变量值。断点调试是一种较为直观的程序调试方式，它通过设置断点跟踪变量的取值，观察运行结果，进行程序调试。断点调试的基本方法为：
进入调试状态；
设置断点；
检查运行状态下各个变量的值，确定错误的位置，并进行修改；
反复调试直至程序运行正确。
2. 排序方法
Python 语言中内置了多种排序方法，函数 sort 就是其中常用的一种。
当程序调试、运行正常并得到正确结果后，就实现了前期设计的算法，解决了相应的问题。当然，要想更深入地了解算法与程序设计，还需要进一步学习编程语言、算法设计及数据结构等知识，创造性地利用计算机解决问题。
实践活动
编程查找小说中的主要人物
修改前面编写的《三国演义》小说高频词查找程序，实现功能：找出小说中出场次数最多的 10 位人物。
1. 在前面已经查找到的 20 个高频词中，包含“却说”“二人”“不能”等与人名无关的词语。想一想如何去除这些词语，只显示 10 位出场次数最多的主要人物的人名？试着修改程序。
2. 统计小说中的高频词，不仅可以帮助我们了解其中的主要人物，还可以用来分析人物的主要活动地点及人物间的关系等。试着编程分析自己感兴趣的一本小说，说一说你的发现。
项目实施
丰富“自助式人行过街红绿灯”的功能
一、项目活动
1. 收集学校、医院或居住地周边的马路通行状况（如马路宽度、高峰段、人流量和车流量等信息），思考为其设计“自助式人行过街红绿灯”的合理配时方案，进一步完善程序功能，以实现真实问题求解。
2. 思考如何实现更人性化、智能化的交通管理，设计一种在智能交通环境下，控制十字路口红绿灯时长变化的合理方案，并在小组间交流展示。
建议：结合物联网和大数据技术为智能交通带来的新可能，有效整合多维的、海量的数据，挖掘各种交通数据之间的联系，思考精准化、人性化设计或提升交通智能化管理的策略，尝试描述相应的解决方案。
二、项目检查
1. 结合实际情况，优化“自助式人行过街红绿灯”程序功能，调试运行程序，完成项目。
2. 科学设计和完善交通智能化管理的方案。
课后作业
1. 交通信号“绿波带”是根据车辆运行情况对各路口红绿灯进行协调，使车辆通过路口时能连续获得一路绿灯。某路段启用了“绿波带”技术，如图 2.4.8 （参见教材P81）所示，全长1.6 km，5 个灯控路口，提示的“绿波速度”为 60 km/h，假设 5 个灯控路口间距相等。在仅考虑一辆车通行的情况下，如果实现“绿波”交通，那么相邻两个路口间绿灯亮起的最大时间间隔应该设置为多少？思考该问题求解的算法并编程实现。
2. 韩信是汉初著名军事家，传说他统计士兵数目有个独特的方法。例如，先令士兵排成 5 列纵队，结果余 1 人；接着，命令士兵排成 6 列纵队，结果余 5 人；再命令士兵排成 7列纵队，结果余 4 人；最后，命令士兵排成 11 列纵队，结果余 10 人。这样他便知道士兵的总人数了。这种计数的方法被后人称为“韩信点兵”。试编写程序计算士兵的数目。
3. 编写程序，统计一段文本中分别有多少个汉字、英文字母、数字和其他字符。
板书设计
第 2 章 算法与程序实现
2.4 常见算法的程序实现
1.基于解析算法的问题解决
2基于枚举算法的问题解决
3.算法与程序实现的综合应用
普通高中教科书
信息技术　必 修 1　数据与计算
编著
人民教育出版衬课程教材研究所信息技术课程教材研究开发中心
中国地图出版社教材出版分社
总 主 编 ：祝智庭 樊 磊
副总主编 ：高淑印 郭 芳 李 锋
本册主编 ：李 锋 高淑印
编写人员 ：程建娜 刘姝弘 夏燕萍 王 岚 史弘文

展开更多......

收起↑