“算法設(shè)計(jì)與分析”中經(jīng)典算法動(dòng)態(tài)演示軟件的設(shè)計(jì)與實(shí)現(xiàn)

郭良敏++孫圳昊++羅永龍++胡桂銀++左開(kāi)中

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

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

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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#

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

1 整體框架

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

2 具體實(shí)現(xiàn)

2.1 分治法

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

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

2.2 貪心法

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

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

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

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

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

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

2.4 回溯法

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

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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