秦敏，王井阳，乔世权

（河北科技大学 信息科学与工程学院，河北石家庄 050018）

作为问题求解和程序设计的重要基础——算法设计与分析在计算机科学与技术专业的课程体系中是一门重要的必修课，通过该课程的学习，不但为学习其他专业课程奠定了扎实的基础，也对培养学生的逻辑思维和创造性起着不可替代的作用[1]。算法课程作为计算机学科的一门专业核心课程，尤其注重培养学生算法基本理论知识和计算思维、问题建模、算法设计与分析能力[2]。

1 教学目标

本课程是计算机科学与技术专业的重要课程，由于课程的难度比较大，那么课程要达到什么目标，如何讲授好这门课就是值得探讨的课题。目标定得太高和太低都不可行，在这里给出本学校关于这门课的教学目标，希望和大家探讨。本课程是为让学生掌握经典算法，学会用算法编程解决实际问题而设立。通过本课程的学习，使学生能够掌握经典算法，并且能够使用C 语言编程实现算法，以案例为驱动，理解算法开发过程，最终达到能够进行问题建模并用算法进行分析和设计的目标。

2 基于COID 的讨论式案例教学模式

为了充分发挥学生的主动性，让学生成为主体，并不断提高学生解决问题的能力和编程能力，借鉴CDIO 思想进行了教学模式的设计，称为“基于COID的讨论式案例教学模式”。CDIO 思想是国际工程教育的通用思想，即构思（Conceive）、设计（Design）、实现（Implement）、运作（Operate）[3]。在这个模式里教师提出案例问题，学生思考解决问题的算法策略，并编程实现，最后教师主持学生讨论，比如从案例中发现的算法间的区别，以及比较谁的方法最优，即哪种算法具有最小的时间复杂度或空间复杂度。在这个过程中，教师和学生的任务如表1所示。

表1 基于CDIO 的讨论式案例教学模式表

每一个案例都经过上述四个过程，经过几个案例之后，学生的编程能力显着提高。在案例的指导和讨论中，主要注意以下几个方面：比较算法策略之间的关系，讨论谁的方法最优，以及思维方法的渗透。

2.1 比较算法策略之间的关系

由于课本重点是讲算法策略，对策略之间的关系并没有特别说明。如何才能让学生更好地理解算法策略，这里采用了通过案例来进行算法策略比较的方法。例如分治策略是将原问题分解为若干个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。因为在求解大问题时，需要递归地求解小问题，因此一般用递归的方法实现，即自顶向下。动态规划把求解过程变成一个多步判断的过程，每一步都对应某个子问题，算法细心地划分子问题的边界，从小的子问题开始，逐层向上求解，通过子问题之间的依赖关系，有效利用前面已经得到的结果，最大限度减少重复工作，以提高算法效率[1]。

分治策略和动态规划都是将原问题分解为若干个规模较小的子问题，求解这些子问题（Conquer），然后再合并这些子问题的解来建立原问题的解，那么这两个算法策略之间的区别是什么呢？是否所有能用动态规划解决的问题都可以用分治策略解决呢？区别在于这些子问题是否会有依赖，子问题在求解后，可能会再次求解，于是需要将这些子问题的解存储起来，当下次再次求解这个子问题时，可以直接使用。动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决，从而只需更少的运行时间。即用动态规划能解决的问题，分治策略肯定能解决，只是运行时间更长。因此，分治策略一般用来解决子问题相互独立的情况，各个子问题之间不能有依赖关系，称为标准分治，而动态规划用来解决子问题之间有依赖的情况。为了让学生理解这一点，设计了两个案例。案例“安排比赛日程表”要求按某种规则安排n 个选手的比赛日程表，当n 比较大时，手动已无法安排，只能采用分治策略，安排n 个选手分成安排两个n/2 的选手，依次类推直到人数少到可以安排为止，这是一个分治策略的案例。“求图中两点间的最短路径”是一个动态规划的案例，通过这两个案例来让学生体会两个算法策略的区别。

再比如动态规划一般由两种方法来实现，一种为自顶向下的备忘录方式，用递归实现，一种为自底向上的方式，用递推实现。“求图中两点间的最短路径”要求学生用两种方法编程，体会其中的区别。并用动态规划和分治策略两种算法策略求解“求图中两点间的最短路径”，比较哪种更合适，进而思考什么情况下更适合用动态规划策略，什么情况下更适合用分治策略？再比如既然动态规划通常用递推来实现，那么它与递推之间是什么关系？动态规划求解的多阶段决策问题必须满足最优子结构特性，而递推所求解的问题则无须满足。动态规划求解的是最优化问题，递推求解的是判定性问题、构造性或计数性问题。比如“整币兑零”若求解最少零币个数属于求最优解，可以采用动态规划算法，如果求解的是不同的兑换种数则是计数性问题，只能采用递推算法。再比如“0-1 背包问题”，是算法课程中动态规划策略教学的重要内容。0-1 背包问题可描述为：存在1 个有限容量的背包和一组有限个数的物品，已知背包的容量以及每个物品的重量和价值，如何选择装入背包的物品，使得在不超过背包容量的前提下装入背包的物品的总价值最大[4]。这是一个典型的动态规划算法策略的问题，而动态规划算法随着背包容量增大、物品数量增加，其运行时间逐渐增加。贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解，是一种近似算法。从求解效率来说，贪心算法比动态规划更高，可以使用“0-1 背包问题”案例让学生比较两种算法的运行时间，进而让学生理解当求解最优解时间太长的话那么接受一个近似解也是可以的。

2.2 讨论谁的方法最优

在案例评价阶段，要组织学生讨论比较谁的方法最优，比如“韩信点兵”这个案例，韩信在点兵的时候，为了知道有多少个士兵，同时又能保住军事机密，便让士兵排队报数。按从1 至5 报数，记下最末一个士兵的数为1；再按从1 至6 报数，记下最末一个士兵的数为5；再按从1 至7 报数，记下最末一个士兵的数为4；再按从1 至11 报数，记下最末一个士兵的数为10。韩信至少有多少兵？韩信点兵是一个典型的枚举算法的案例，但并不是一个一个数值地枚举，如何枚举才能枚举次数最少，运行时间最短，学生提出了各种各样的方案。

方案1：初始值40，步长30 的方案，程序结果显示枚举次数为70 次。

方案2：初始值65，步长66 的方案，程序结果显示枚举次数为32 次。

方案3：初始值32，步长77 的方案，程序结果显示枚举次数为28 次。

还有各种其他方案，通过对这些方案的比较，学生对枚举的认识进一步提高。再比如“求图中两点间的最短路径”，就图的存储，有的学生存储了图中所有的点和所有的边，有的学生则知道这是一个邻接矩阵。邻接矩阵是一个对称的矩阵，因为A 点到B 点的距离为X，B 点到A 点的距离也为X，所以只保存上三角就可以了，减少了空间复杂度。而在算法上有的学生采用“Dijkstra”算法，有的学生采用动态规划算法，可以就不同的图，比较两种算法的运行时间。总之通过设置案例让学生编程，然后互相讨论互相比较，一方面教学相长，另一方面也提高了学生的编程能力。

2.3 思维方法的渗透

国内教材大部分都是按照基本算法策略进行章节划分，它们主要以分治法、贪心法、动态规划法、回溯法、分枝限界法等算法策略来组织内容，这样有利于学生着重体会各种算法的思想[5]。这种教学方式的优点是学生在遇到具体问题时往往能够较快地选择合适的算法策略作为解题思路，然后根据现有算法作一定的变换后找到新问题的解决方法；缺点是对于那些无法明确归类为某种算法策略的问题则可能无法迅速找到解题思路。所以在教学过程中有意识渗透一些科学思维方法，比如比较与分类方法、顺向思维与逆向思维方法、分析与整合方法、发散与收敛方法、搭桥过河方法和模糊性思维方法等。如果遇到无法明确归类为某种算法策略的问题，学生可以从更高一级的思维方法出发，来找到解题的思路。在教学中有意识地讲解科学的思维方法，不但有助于学生学习，而且有助于学生开阔思路，对于学生以后的人生也有帮助。

比较与分类方法是贯穿始终的，比如回溯法与枚举法的比较、递推与递归的比较、递归与动态规划的比较、动态规划与分治策略之间的比较等[6]。枚举法和回溯法都属于搜索技术，动态规划和分治策略都属于分析与整合方法，诸如此类的分类有助于学生的总结和理解。顺向思维与逆向思维方法也是经常用到的，比如递推有顺推有逆推，采用哪种递推须根据实际情况来定。在编程中更是经常把乘法变成除法或者除法变成乘法、开方变成平方或者平方变成开方等。分析与整合方法，整个程序设计是结构化的、是分模块的，很多算法也体现了分析和整合方法，比如递推、动态规划和分治策略。发散与收敛方法，教学中采用的讨论式案例教学法就是一种发散与收敛方法，把案例布置下去，学生提出不同的解决方案，这属于发散，再讨论比较找出最佳方案，这属于收敛。模糊性思维方法，在自然界与日常生活中，许多现象带有不确定性，很难建立确切的数学模型，也不是所有问题都要求最优解，这时就用到了模拟算法和贪心算法。表2给出了部分算法和思维方法之间的分类联系。

表2 算法和思维方法之间的分类联系

3 结语

算法作为一门比较难学的课程，如何才能讲授好这门课是很多教师需要讨论的问题。案例式教学可以发挥学生的主动性，提高学生分析问题和解决问题的能力。本文根据COID 思想提出了一种讨论式案例教学法供大家探讨，强调在教学过程中对算法的比较和程序的优化，并建议从更高一级的思维方法入手，进一步开阔学生的思路。