分治算法求解棋盘覆盖问题的互动教学过程

《分治算法求解棋盘覆盖问题的互动教学过程》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分治算法求解棋盘覆盖问题的互动教学过程摘要：针对算法设计与分析课程难度较大、对学生编程能力要求较高的现状，通过对棋盘覆盖问题的分治算法求解过程进行互动教学设计，引导学生进行问题理解、算法设计、算法实现。特别是在算法实现环节，一行一行地动态展示程序的编写过程，同时充分考虑学生现有的编程基础，采用程序填空的形式降低学生编程难度，有助于消除学生的畏难心理，有效提高了学生的学习兴趣，同时锻炼了学生的计算思维。中国8/vie　　关键词：棋盘覆盖；递归；分治；互动教学　　中图分类号：TP301文献标识码：A：1009-3044（2016）35-0146-02　　In

2、teractiveTeachingProcedureofthe“DivideandConquer”Algorithmof“ChessBoard”　　LVLan-lan，LIMing　　（DepartmentofSoftationEngineering，HunanUniversityofScienceandEngineering，Yongzhou425100，China）　　Abstract：Thecourseofalgorithmdesignandanalysisisdifficulttothosestudentsmingability.Thispape

3、rdescribestheinteractiveteachingdesignofthe“divideandconquer”algorithmof“chessboard”，，designandimplementthealgorithm.Especiallyduringthephaseofalgorithmimplementation，mingtostudentslinebyline.Atthesametime，pletion”tomakeprogrammingeasyforstudents.Itishelptoeliminatestudents’fear，

4、inspiretheirinterestandtraintheirputationalthinking.　　Keywords：chessboard；recursion；divideandconquer；interactiveteaching　　1引言　　�λ惴ǖ难芯恳丫�被公认为是计算机科学的基石，算法设计与分析课程也是我校软件工程专业的一门专业核心课程，学习算法的重要性毋庸置疑。但算法设计与分析课程具有难度大，对学生编程能力要求高的特点，不少学生望而却步。在教学过程中我们发现，虽然大部分学生能正确理解算法的思路，但是却不能以某种高级程序设计语言实现算法

5、。针对学生这种“眼高手低”的现状，本文提出将“程序填空”这一程序设计类课程考试中常用的题型，应用到算法设计与分析课程日常教学中，通过实施互动教学降低课程难度、激发学生兴趣。我们以分治法求解棋盘覆盖问题为例，逐步引导学生完成从算法的思路解析到完整实现的全过程，聚焦从算法到程序的“最后一公里”。　　2棋盘覆盖问题　　2.1问题描述　　棋盘覆盖问题是许多国内教材[1-2]在阐述分治法时使用的一个经典案例，具体描述如下：　　在一个个方格组成的棋盘中，若恰有一个方格与其它方格不同，则称该方格为一特殊方格，称该棋盘为一特殊棋盘。图1为k=2时的一个特殊棋盘，其中特殊

6、方格的位置是（1，2），用阴影表示。　　在棋盘覆盖问题中，要用图2中4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。　　图棋盘覆盖问题的已知条件是在一个的棋盘上有一个特殊方格，因此算法的输入可以用来表示棋盘的大小，用（dr，dc）来表示特殊方格在棋盘中的位置。棋盘覆盖问题的输出结果是一个覆盖了L形骨牌的棋盘，如何表示三个方格被同一个L形骨牌覆盖称为关键。学生比较容易想到的方法是使用同一种颜色来填充被同一个L形骨牌覆盖的三个方格，这是一种形象化的思维方式。为了将数据抽象成程序设计语言方便处理的形式，可

7、以从颜色在计算机中的存储形式（整数）出发，引导学生直接使用整数来填充表示被同一个L形骨牌覆盖的三个方格。这样就完成了棋盘覆盖问题中输入/输出数据的抽象，并且可以得到函数的原型：voidChessBoard（intsize，intdr，intdc，int**board）。　　3.3.2C++实现　　根据3.3.1中的数据抽象结果得到函数原型后，进行算法实现时，还有2个待解决的关键问题。第一，如何确定递归函数ChessBoard的停止条件。大部分学生认为是最简单的情况是当的时候，即：的棋盘中有一个特殊方格，此时剩余的3个方格刚好可以用一个L形骨牌来覆盖。但事

8、实上更简单的情况是当的时候，即：的棋盘中有一个特殊方格，此时根本无需任何覆盖。因