分治算法求解棋盘覆盖问题互动教学过程摘要：针对算法设计与分析课程难度较大、对学生编程能力要求较高的现状，通过对棋盘覆盖问题的分治算法求解过程进行互动教学设计，引导学生进行问题理解、算法设计、算法实现。特别是在算法实现环节，一行一行地动态展示程序的编写过程，同时充分考虑学生现有的编程基础，采用程序填空的形式降低学生编程难度，有助于消除学生的畏难心理，有效提高了学生的学习兴趣，同时锻炼了学生的计算思维关键词：棋盘覆盖；递归；分治；互动教学中图分类号：TP301文献标识码：A文章编号：1009-3044（2016）35-0146-02InteractiveTeachingProcedureofthe“DivideandConquer”AlgorithmwiththeProblemof“ChessBoard”LVLan-lan，LIMing（DepartmentofSoftwareEngineering，CollegeofElectronicandInformationEngineering，HunanUniversityofScienceandEngineering，Yongzhou425100，China）Abstract：Thecourseofalgorithmdesignandanalysisisdifficulttothosestudentswithpoorprogrammingability.Thispaperdescribestheinteractiveteachingdesignofthe“divideandconquer”algorithmwiththeproblemof“chessboard”，whichincludesdirectingstudentstounderstandtheproblem，designandimplementthealgorithm.Especiallyduringthephaseofalgorithmimplementation，weshowtheprocedureofprogrammingtostudentslinebyline.Atthesametime，weuse“programcompletion”tomakeprogrammingeasyforstudents.Itishelptoeliminatestudents’fear，inspiretheirinterestandtraintheircomputationalthinking.Keywords：chessboard；recursion；divideandconquer；interactiveteaching1引言�λ惴ǖ难芯恳丫�被公认为是计算机科学的基石，算法设计与分析课程也是我校软件工程专业的一门专业核心课程，学习算法的重要性毋庸置疑。但算法设计与分析课程具有难度大，对学生编程能力要求高的特点，不少学生望而却步。在教学过程中我们发现，虽然大部分学生能正确理解算法的思路，但是却不能以某种高级程序设计语言实现算法。针对学生这种“眼高手低”的现状，本文提出将“程序填空”这一程序设计类课程考试中常用的题型，应用到算法设计与分析课程日常教学中，通过实施互动教学降低课程难度、激发学生兴趣。我们以分治法求解棋盘覆盖问题为例，逐步引导学生完成从算法的思路解析到完整实现的全过程，聚焦从算法到程序的“最后一公里”2棋盘覆盖问题2.1问题描述棋盘覆盖问题是许多国内教材[1-2]在阐述分治法时使用的一个经典案例，具体描述如下：在一个个方格组成的棋盘中，若恰有一个方格与其它方格不同，则称该方格为一特殊方格，称该棋盘为一特殊棋盘。图1为k=2时的一个特殊棋盘，其中特殊方格的位置是（1，2），用阴影表示在棋盘覆盖问题中，要用图2中4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖图棋盘覆盖问题的已知条件是在一个的棋盘上有一个特殊方格，因此算法的输入可以用来表示棋盘的大小，用（dr，dc）来表示特殊方格在棋盘中的位置。棋盘覆盖问题的输出结果是一个覆盖了L形骨牌的棋盘，如何表示三个方格被同一个L形骨牌覆盖称为关键。学生比较容易想到的方法是使用同一种颜色来填充被同一个L形骨牌覆盖的三个方格，这是一种形象化的思维方式。为了将数据抽象成程序设计语言方便处理的形式，可以从颜色在计算机中的存储形式（整数）出发，引导学生直接使用整数来填充表示被同一个L形骨牌覆盖的三个方格。这样就完成了棋盘覆盖问题中输入/输出数据的抽象，并且可以得到函数的原型：voidChessBoard（intsize，intdr，intdc，int**board）3.3.2C++实现根据3.3.1中的数据抽象结果得到函数原型后，进行算法实现时，还有2个待解决的关键问题。第一，如何确定递归函数ChessBoard的停止条件。大部分学生认为是最简单的情况是当的时候，即：的棋盘中有一个特殊方格，此时剩余的3个方格刚好可以用一个L形骨牌来覆盖。但事实上更简单的情况是当的时候，即：的棋盘中有一个特殊方格，此时根本无需任何覆盖。因此...