郭良敏++孫圳昊++羅永龍++胡桂銀++左開中

摘要：基于WPF和C#在Visual Studio 2010環(huán)境下，設(shè)計并實現(xiàn)了一款“算法設(shè)計與分析”課程的學(xué)習(xí)軟件。該軟件選取了冒泡排序、8皇后問題、漢諾塔問題、背包問題分別作為貪心法、回溯法、分治法、動態(tài)規(guī)劃法的演示實例，力圖生動展示經(jīng)典算法的執(zhí)行過程。

關(guān)鍵詞：算法設(shè)計與分析課程；動態(tài)演示；WPF；C#

中圖分類號：TP311 文獻標(biāo)識碼：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#

算法演示程序是以圖形解釋算法，動態(tài)演示能夠幫助學(xué)生加深算法理解，在腦海中形成算法執(zhí)行過程的直觀生動的印象，進而提高算法的教學(xué)效果[1]。許多算法演示系統(tǒng)的設(shè)計與實現(xiàn)的思想都來源于M.Brown等制作的BLASA系統(tǒng)[2]，隨著可視化技術(shù)的發(fā)展，算法演示程序能夠更加生動地展現(xiàn)出求解問題的過程。一個良好的演示系統(tǒng)應(yīng)當(dāng)具有豐富的媒體表現(xiàn)力、深入的細節(jié)演示效果、靈活的交互能力以及適當(dāng)?shù)挠螒蚬δ芩膫€特性[3]。

1 整體框架

本軟件基于微軟推出的用戶界面框架WPF[4-5]，并在Visual Studio 2010平臺下設(shè)計與開發(fā)的。它提供了可視化界面，用戶可直觀看到分治法、貪心法、動態(tài)規(guī)劃法和回溯法四種經(jīng)典算法策略的求解過程[6]，軟件的整體框架如圖1所示。

2 具體實現(xiàn)

2.1 分治法

本文選擇了漢諾塔問題進行分治算法的演示。漢諾塔問題中，每個盤子在柱子上的運作方式與棧結(jié)構(gòu)非常類似：只能移動最上面的盤子。程序中設(shè)置了三個棧用于模擬當(dāng)前三個柱子的狀態(tài)。

盤子在移動過程中只涉及了四個方向：向上出盤、向左或右邊移動、向下入盤。程序設(shè)置了一個方向變量direction，出盤過程中，盤子在越過柱子頂部時始終保持了方向direction=0。進程在發(fā)現(xiàn)direction為0時會控制盤子一次向上移動一個單位，當(dāng)盤子的下邊界越過了柱子的上邊界，direction改變，根據(jù)相應(yīng)信息，將direction設(shè)置為向左或者向右方向，左右移動過程以及向下入盤過程的移動方式和判斷方法和出盤過程類似，不再贅述。

2.2 貪心法

選取冒泡排序演示貪心算法。我們采用球來表示每一個待排元素[7]，并用其透明度表示元素值的大小。用戶輸入球體的數(shù)目和初試排列狀態(tài)（程序提供了三種狀態(tài)：隨機排列、逆序排列、正序排列）后，系統(tǒng)內(nèi)部動態(tài)分配等長的球體數(shù)組。這些元素都是實例化的對象，能夠被添加到畫布上。

利用WPF中的Double Animation動畫類來實現(xiàn)，它通過指定一個double類型的初始值From和同類型的終值To，使被關(guān)聯(lián)的控件形成動畫。如：以下代碼可實現(xiàn)Name為lblTest的控件在一秒鐘的時間內(nèi)寬度增加50的動態(tài)效果。同樣，球體在畫布中的位置也是屬性，可用動畫改變。

一般排序算法都分為兩個基本操作：比較和交換。本軟件的冒泡排序演示程序就是利用這兩個基本操作來進行演示的。如圖2所示，若無需交換，則給出提示文字；若需要交換，則利用動畫將相應(yīng)兩個球的位置顛倒。

2.3 動態(tài)規(guī)劃法

本文選擇0-1背包問題演示動態(tài)規(guī)劃法。具體演示過程：用戶完成輸入后，點擊演示進入演示狀態(tài)。程序采用單步演示的方式，用戶單擊按鈕，程序演示一步。利用二維數(shù)組的列數(shù)代表背包的總重量，用戶可以修改。程序中使用Grid控件模擬二維數(shù)組，Grid內(nèi)部的Label控件需要動態(tài)生成，見如下代碼。其中thingCount為物品總數(shù)，bagWeight為背包承重，lblC是用于方便訪問指定單元格的Label而設(shè)置的Label類型數(shù)組。

動態(tài)規(guī)劃求中間值的代碼如下。其中，第005行的判斷表示當(dāng)前第i個物品的價值與前i-1個物品在背包承重為j-W_arr[i]時的最大價值之和，是否比前i-1個物品在背包承重為j時的最大價值高。

2.4 回溯法

本文選擇8皇后問題演示回溯法，圖3和4是8皇后問題的相關(guān)演示效果圖。演示程序中有一個皇后放置的試探過程，如圖3所示，黑色棋子表示當(dāng)前已放好的皇后位置，紅色的棋子表示正在試探中。若紅色棋子試探成功，則將黑色棋子放在該位置。

在該程序的另一個功能中，用戶可以自己放置棋子，來感受8皇后的探索過程。本程序提供了一個錯誤提示的小功能，若當(dāng)前棋子與棋盤上某個棋子有沖突，即在同行同列或者同一對角線，那么就會有紅線閃爍，表明無法放置，如圖4所示。

3 結(jié)束語

本軟件在設(shè)計過程中，參照良好算法演示系統(tǒng)的設(shè)計要求，提供了交互功能和圖形演示跟蹤的功能。在算法的教學(xué)過程中能讓學(xué)生接觸直觀的操作演示，可更好地讓學(xué)生知其所以然[8]，也更快地讓學(xué)生具有利用計算機解決問題的思維方式。不足之處在于它不支持算法跟蹤功能，無法從代碼上深刻認(rèn)識算法。

參考文獻：

[1]Matthew MacDonald著， 王德才 譯. WPF編程寶典——C#2010版[M].

[2]劉鐵猛. 深入淺出WPF[M]. 北京： 水利電力出版社， 2010.

[3]陳慧南. 算法設(shè)計與分析——C++語言描述[M]. 2版.北京： 電子工業(yè)出版社， 2012.

[4]孫永新， 閆大順. 動畫演示與算法教學(xué)研究[J]. 現(xiàn)代計算機， 2009（10）： 81-83

[5]張文升， 周青云， 周曉聰. 算法演示系統(tǒng)研究與應(yīng)用[J]. 計算機應(yīng)用與軟件， 2008， 10：41-43.

[6]李健. 漢諾塔算法演示系統(tǒng)的設(shè)計與實現(xiàn)[J]. 現(xiàn)代計算機， 2011（24）： 76-80.

[7]田軍， 李豐軍. 基于VB程序的冒泡排序算法演示[J]. 電腦知識與技術(shù)， 2011（36）： 9410-9412.

[8]楊樹林. 算法演示軟件的設(shè)計思路、實現(xiàn)方法及技術(shù)[J]. 北京印刷學(xué)院學(xué)報， 2003，11（3）.