郭良敏++孙圳昊++罗永龙++胡桂银++左开中

摘要：基于WPF和C#在Visual Studio 2010环境下，设计并实现了一款“算法设计与分析”课程的学习软件。该软件选取了冒泡排序、8皇后问题、汉诺塔问题、背包问题分别作为贪心法、回溯法、分治法、动态规划法的演示实例，力图生动展示经典算法的执行过程。

关键词：算法设计与分析课程；动态演示；WPF；C#

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）20-0078-02

Abstract： A learning software of algorithm design and analysis course is designed and implemented by using WPF and C# language under the environment of Visual Studio 2010. The bubble sort， the eight queen problem， the tower of Hanoi problem and the knapsack problem are chosen as demonstration of the greedy method， backtracking method， divide and conquer method and dynamic programming， trying to vividly display the demonstration process of above classical algorithms.

Key words： Algorithm design and analysis course； Dynamic demonstration； WPF； C#

算法演示程序是以图形解释算法，动态演示能够帮助学生加深算法理解，在脑海中形成算法执行过程的直观生动的印象，进而提高算法的教学效果[1]。许多算法演示系统的设计与实现的思想都来源于M.Brown等制作的BLASA系统[2]，随着可视化技术的发展，算法演示程序能够更加生动地展现出求解问题的过程。一个良好的演示系统应当具有丰富的媒体表现力、深入的细节演示效果、灵活的交互能力以及适当的游戏功能四个特性[3]。

1 整体框架

本软件基于微软推出的用户界面框架WPF[4-5]，并在Visual Studio 2010平台下设计与开发的。它提供了可视化界面，用户可直观看到分治法、贪心法、动态规划法和回溯法四种经典算法策略的求解过程[6]，软件的整体框架如图1所示。

2 具体实现

2.1 分治法

本文选择了汉诺塔问题进行分治算法的演示。汉诺塔问题中，每个盘子在柱子上的运作方式与栈结构非常类似：只能移动最上面的盘子。程序中设置了三个栈用于模拟当前三个柱子的状态。

盘子在移动过程中只涉及了四个方向：向上出盘、向左或右边移动、向下入盘。程序设置了一个方向变量direction，出盘过程中，盘子在越过柱子顶部时始终保持了方向direction=0。进程在发现direction为0时会控制盘子一次向上移动一个单位，当盘子的下边界越过了柱子的上边界，direction改变，根据相应信息，将direction设置为向左或者向右方向，左右移动过程以及向下入盘过程的移动方式和判断方法和出盘过程类似，不再赘述。

2.2 贪心法

选取冒泡排序演示贪心算法。我们采用球来表示每一个待排元素[7]，并用其透明度表示元素值的大小。用户输入球体的数目和初试排列状态（程序提供了三种状态：随机排列、逆序排列、正序排列）后，系统内部动态分配等长的球体数组。这些元素都是实例化的对象，能够被添加到画布上。

利用WPF中的Double Animation动画类来实现，它通过指定一个double类型的初始值From和同类型的终值To，使被关联的控件形成动画。如：以下代码可实现Name为lblTest的控件在一秒钟的时间内宽度增加50的动态效果。同样，球体在画布中的位置也是属性，可用动画改变。

一般排序算法都分为两个基本操作：比较和交换。本软件的冒泡排序演示程序就是利用这两个基本操作来进行演示的。如图2所示，若无需交换，则给出提示文字；若需要交换，则利用动画将相应两个球的位置颠倒。

2.3 动态规划法

本文选择0-1背包问题演示动态规划法。具体演示过程：用户完成输入后，点击演示进入演示状态。程序采用单步演示的方式，用户单击按钮，程序演示一步。利用二维数组的列数代表背包的总重量，用户可以修改。程序中使用Grid控件模拟二维数组，Grid内部的Label控件需要动态生成，见如下代码。其中thingCount为物品总数，bagWeight为背包承重，lblC是用于方便访问指定单元格的Label而设置的Label类型数组。

动态规划求中间值的代码如下。其中，第005行的判断表示当前第i个物品的价值与前i-1个物品在背包承重为j-W_arr[i]时的最大价值之和，是否比前i-1个物品在背包承重为j时的最大价值高。

2.4 回溯法

本文选择8皇后问题演示回溯法，图3和4是8皇后问题的相关演示效果图。演示程序中有一个皇后放置的试探过程，如图3所示，黑色棋子表示当前已放好的皇后位置，红色的棋子表示正在试探中。若红色棋子试探成功，则将黑色棋子放在该位置。

在该程序的另一个功能中，用户可以自己放置棋子，来感受8皇后的探索过程。本程序提供了一个错误提示的小功能，若当前棋子与棋盘上某个棋子有冲突，即在同行同列或者同一对角线，那么就会有红线闪烁，表明无法放置，如图4所示。

3 结束语

本软件在设计过程中，参照良好算法演示系统的设计要求，提供了交互功能和图形演示跟踪的功能。在算法的教学过程中能让学生接触直观的操作演示，可更好地让学生知其所以然[8]，也更快地让学生具有利用计算机解决问题的思维方式。不足之处在于它不支持算法跟踪功能，无法从代码上深刻认识算法。

参考文献：

[1]Matthew MacDonald著， 王德才 译. WPF编程宝典——C#2010版[M].

[2]刘铁猛. 深入浅出WPF[M]. 北京： 水利电力出版社， 2010.

[3]陈慧南. 算法设计与分析——C++语言描述[M]. 2版.北京： 电子工业出版社， 2012.

[4]孙永新， 闫大顺. 动画演示与算法教学研究[J]. 现代计算机， 2009（10）： 81-83

[5]张文升， 周青云， 周晓聪. 算法演示系统研究与应用[J]. 计算机应用与软件， 2008， 10：41-43.

[6]李健. 汉诺塔算法演示系统的设计与实现[J]. 现代计算机， 2011（24）： 76-80.

[7]田军， 李丰军. 基于VB程序的冒泡排序算法演示[J]. 电脑知识与技术， 2011（36）： 9410-9412.

[8]杨树林. 算法演示软件的设计思路、实现方法及技术[J]. 北京印刷学院学报， 2003，11（3）.