第７期 ２０１８年７月１０日 计算机教育 Ｃｏｍｐｕｔｅｒ Ｅｄｕｃａｔｉｏｎ 文章编号：１６７２—５９１３（２０１８）０７—０１１１—０３ 中图分类号：Ｇ６４２ 面向计算思维培养的算法教学案例 李旭，赵秀岩，康丽，沈岚，姚春龙 （大连工业大学信息科学与工程学院，辽宁大连１１６０３４） 摘要：针对非计算机专业学生学习计算机基础课程后不能学以致用的问题，提出以思维培养为切入 点进行教学改革，精心设计以问题为驱动的教学案例，引导学生对现实问题进行建模、分析、比较、 抽象，利用流程图描述解决问题的步骤，通过改革教学方法，变知识的传授为思维的训练，激发学生 对计算机科学的兴趣，使学生热爱计算机科学并积极探索，真正将计算思维融入后续的专业学习和一 切活动中。 关键词：思维培养；问题解决；思维过程；计算机基础课程 ０ 引言 算思维代表着一种普遍的认识和一类普适的技 能，在科学技术日新月异的信息时代，我们每一 计算机基础课程是高等院校非计算机专业 个人都应该热心于它的学习和运用。然而目前对 学生的计算机入门课程，旨在培养学生利用计算 于计算思维能力培养的认识，一定程度上还停留 机去获取、分析、加工、处理、传递信息，解决 在对国外思想的吸收和消化阶段。如何让计算思 实际问题的思路和能力，为将来使用计算机解决 维能力培养在课程教学中真正落地是需要深入探 各自专业问题打下良好的基础。然而，根据多年 讨和解决的问题。 的授课情况看，学生在学完整门课程后虽然能够 了解和掌握大学计算机基础课程的基本知识和技 １ 传统算法教学中存在的问题 能，但是往往不能系统、全面地认识和应用这些 知识，在后续的专业学习中遇到问题时，想不到 思考和解决问题的能力是高校人才培养 用计算机知识去解决，或者想使用计算机却不知 的目标之一。美国著名心理学和计算机专家西蒙 道如何应用学过的知识。因此，为了更好发挥计 指出：当一个人接受一项任务，但又不知道如何 算机基础课程在高校人才培养课程体系中的基础 去完成它时，他面临的就是一个问题。西蒙将问 支撑作用，培养出适合时代需要的具有创新思维 题解决看做人类认知的三类信息加工过程之一。 和综合应用能力的各领域专业人才，开展从“基 为解决某一特定问题而设计的确定的有限的步骤 于知识的技能传授”向“基于应用的思维能力培 称为算法。算法设计与分析在培养学生思考、 养”转变的计算机基础课程教学改革是必要且迫 分析问题和解决问题能力方面具有重要作用。 切的。 然而在传统的算法教学中，教师往往将教学 ２００６年３月，美国卡耐基·梅隆大学计算机 重点放在算法的解释上，教学方法通常采用“介 科学系主任周以真首次提出并定义计算思维的概 绍一举例一演示”三部曲教学法。算法解释生涩 念，周教授认为计算思维是运用计算机科学的基 乏味、案例选取不接地气没有吸引力，学生感觉 础概念进行问题求解、系统设计、人类行为理解 没有实际应用价值。这种授课方式下往往是老师 等涵盖计算机科学广度的一系列思维活动［１】。计 讲、学生听，留给学生主动思考的空间少，久而 基金项目：大连工业大学教育教学改革研究项目（ＪＧＬＸ１６０８４、ＪＧＬＸ１６０３７、ＪＧＬＸ１６０４３）。 第一作者简介：李旭，女，副教授，研究方向为自然语言处理、机器学习，ｌｉｘｕ１０２＠ａｌｉｙｕｎ．ＣＯｒｎ。 计算机教育 Ｉ１２ Ｃｏｍｐｕｔｅｒ Ｅｄｕｃａｔｉｏｎ ２０ｌ８ 久之使学生思维退化，导致懒学甚至厌学 在面向思维培养的计算机基础教学改革实 施以来，我们充分认识到算法教学对培养学生解 决问题能力的重要性，认识到传统的算法教学之 所以效果不佳其根本原冈在于没有掌握算法的本 质——问题的建模、分解、抽象和自动化，在问 题求解过程中没有充分调动学生的主观能动性、 激发学生的求知欲。 ２ 面向思维培养的算法教学改 ｔ．ｊ实践 在实际生活中，图的最小花费生成树ｌ 题 在城市水管、天然气管道规划、最少通信线路铺 设以及物流公司的最小成本分析等领域有着广泛 的应用，它也是算法设计中贪婪法的一个典型问 题。以最小花费问题为例说明面向思维培养的算 法教学改革与实践。 ２．１ 通俗易懂的案例选取 泥泞城市【２ 案例描述如下：假设有一座城市 还未铺上道路，下雨之后要在这座城市中行走是 一件非常困难的事情，地面被雨水浸湿，满是泥 泞，车辆纷纷陷入泥沼之中，人们的鞋子上沾满 了污泥。于是痛下决心，一定要在一些道路 砌上石砖，但是钱必须用在刀刃上，他不想浪费 经费，因此他下达了以下两个要求： （１）必须铺设足够的道路，让每个人都能从 家里沿着铺好的道路到达别人的房子。 （２）所花费的经费越少越好。在两栋房子之间 的道路上铺上的石砖数代表了铺路所需要的费用。 ２．２ 以问题为驱动引导学生主动思考、自主 解决问题 通过设计一连串问题，问题之问有层次渐 进关系，逐步引导学生深入思考、归纳总结，进 而找出并描述解决问题的步骤。对于泥泞城市案 例，设计的问题如下： （１）设想这座小城仅有５栋房子和７条路（图 １）。为了连接所有的房子，且要使用最少的石 砖，房子之间的每个方块代表需在此铺上一块石 砖，哪些道路必须铺上石砖？ （２）将这５栋房子连接起来，至少需要铺几 条路？ （３）如果已经选择在房子Ａ、Ｂ和Ｂ、Ｃ之 间分别铺设石砖，直接从房子Ａ到房子Ｃ的道 Ａ 一．－ ．．．．．． ．～； ： ’．． 童雾 －： 。一 ：幽 ｒ－ －－， 图１泥泞城市 路还要不要铺设？ （４）如果添加一条道路，使没汁方案中产生 了一个“循环路线”，即从一条路离开一栋房子 后还能走另外一条路同到这栋房子，这条道路还 要不要添加？ （５）铺设方法足唯一的么？你能想到的使用 最少石砖数的铺法有几种？ （６）请用自然语言把你铺设最少石砖的ｌ方法 描述出来。 （７）如果用圆圈表示地图中的房子，用线条 和数字表示地图中的道路，计算机科学家们称 这种结构为图。在图中，圆圈代表的房子称为节 点，节点之间的线条代表泥泞的道路，每条道路 的长度用线条旁的数字标明。清画出与上述地图 相对应的图结构。这种将房子缩写成节点、道路 表示为线条和数字的过程称为问题建模。 （８）在图中，如果从一个顶点到另一个顶点 有路径相连，我们称这两个顶点是连通的。如果 图中任意两点都是连通的，该图被称为连通图。 那么上述求地图中连接所有房子的最少石砖数是 不是已经转化为求连通图的总长最短的路径问 题？在计算机科学中该类问题被定义为最小生成 树问题。该问题之所以被称为“最小”是因为它 要求拥有最小的石砖总数，“生成”代表了每一 栋房子都和另外一栋连接起来，最终得到的 Ｆ确 方案的形状看起来则像一棵“树”——如果你从 任一栋房子出发，都会有一条或多条道路从这里 “分又”出去，而这每一条分支稍后又会有其他 的分支，但是两条分支永远无法回指或相交，如 果你让他们相交了，说明将有两条道路能通往同 一栋房子，则其中的一条必是浪费石砖的选择。 （９）如图２所示的大一点城市的布局图，淆 画出与布局图相对应的图结构。 ７ ｊ』『Ｊ 教育与教学研究 增加石砖直到全部房子都被连接起来，注意增加 路径时不能产生循环线路 问题（７）引导学生通过抽象、简化建立能 刻画该类实际问题的一般模型，如图３所示，使 学生水到渠成地得出问题（８）的结论：该问题 即为求解连通图的总长最短的路径问题。 图２大一点的泥泞城市 （１０）是 能应用刚才设计出的最少石砖数 算法，找出大一点城市的石砖铺设方法？这个算 法对于更大规模的相同问题是否依然有效？ （１ ｉ）请川流程图描述铺设最少石砖数的算 图３问题建模 法，即用流程图描述最小生成树算法。 （１２）你是否还能找出其他方法解决该问题？ 清用流程图把解决步骤描述出来。 问题（９）和（１０）引导学生验证算法的正确 性和有效性，归纳总结出求解该类问题的普适算 法。问题（１ １）和（１２）要求学生用流程图准确、 （１３）解决最小花费问题，上述算法的执行 步骤一样吗？哪种方法更优，请说明原因。 对于问题（１）这样小规模的最小花费问题， 规范地描述出算法的步骤，自主“实现”计算机 中经典的Ｋｒｕｓｋａｌ算法或Ｐｒｉｍ算法。问题（１３） 引导学生通过比较执行步数判定算法的性能。 学牛通常很快就能得出最少需铺设７块石砖的 最优方案，也会回答出连接５栋房子，至少需要 铺设４条路。问题（３）和问题（４）能够让学生 ３ 结语 允分思考并明确设计方案中一定不能存在循环线 ｌ路。通过问题（５）和（６）的引导和提问，学生 通常能自主归纳总结出以下两种铺设最少石砖的 上述实例展示了面向计算思维培养的算法教 学改革，在不改变教学大纲和内容的基础上，通 过改进教学方法，有意识地将与思维培养相关的 问题分解、抽象和自动化的方法自然地融人到教 学中，培养了学生思考、主动参与、实际探 究的能力。 方法：①从一张空白地图开始，按照路径长度从 小到大添加道路，逐步增加石砖直到全部房子都 被连接起来，注意增加路径时不能将两个已经连 接的房子再用其他道路连接起来，产生“循环” 精心设计的教学案例，以及学生与老师“风 云际会”的互动过程大大增加了学生对知识的兴 线路。当路径长度相同时，改变添加路径的顺 序，会产生不同的最终布局，但是最后的结果依 然能保持需要石砖的总数最少。②从一个房子开 趣，开启他们探索知识的航程。通过对我校非计 算机专业开展面向思维的算法教学改革实践，学 生的课堂活跃度大大提升，学习积极性、主动性 高涨 始，遍历与该房子或已连接房子相连接的其他房 子，使用连接路径中的最小长度添加道路，逐步 参考文献： ［１］Ｗｉｎｇ Ｊ Ｍ．Ｃｏｍｐｕｔａｔｉｏｎａｌ ｔｈｉｎｋｉｎｇ［Ｊ］Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆｔｈｅＡＣＭ，２００６，４９（３）：１—６． ［２］孙俊峰，杨帆．不插电的计算机科学［Ｍ】．武汉：华中科技大学出版社，２０１０：１４０—１４６． ［３］朱君波，龚沛曾，杨志强，以计算思维为切八点的递归算法教学改革［ＪＪ．计算机教育，２０１７（７）：３０—３３ （编辑：彭远红）
