(上饒師范學院 數(shù)學與計算機科學學院，江西 上饒 334001)

遞歸算法的VBA模擬實驗研究

顏清，苗壯，艾志華，賴鑫生

(上饒師范學院 數(shù)學與計算機科學學院，江西 上饒 334001)

利用Excel的繪圖功能與VBA混合程序設計，獲得算法過程的實時動態(tài)模擬效果，為計算機實驗提供了一個嶄新的解決方案。計算機經(jīng)典算法的VBA模擬實驗有其獨特的優(yōu)點，學生通過模擬實驗，增強了對算法的感性認識，加深了對算法實現(xiàn)過程的理解。實踐表明，基于VBA的計算機經(jīng)典算法模擬實驗，有利于學生的程序設計能力的提高，適合于計算機實驗教學。

VBA；經(jīng)典算法；計算機實驗；模擬

遞歸算法是計算機經(jīng)典算法之一，遞歸算法是一個不斷循環(huán)自我調(diào)用的過程，即指函數(shù)或過程或程序直接或間接調(diào)用自身的現(xiàn)象，對某些復雜的計算十分有效。作為循環(huán)調(diào)用的出口,遞歸算法首先要有一個確切的初始值，即所謂的“基狀態(tài)”。若以參數(shù)n表示問題的復雜度，n的“基狀態(tài)”常選擇1或0，然后就可進入遞歸算法的關鍵過程——遞歸調(diào)用。遞歸調(diào)用過程分為遞推和回歸兩個階段。遞推階段將參數(shù)復雜度由n降低為n-1，是一個復雜度降低的過程，參數(shù)n最終向復雜度1的“基狀態(tài)”逼近而終止；回歸階段是由“基狀態(tài)”的確切解逐級返回的過程，由“基狀態(tài)”依次獲取參數(shù)的復雜度遞增至n的解為止。在工程應用中，應用參數(shù)n的地方十分常見，如重慶大學李海生利用遞歸算法對單一尺寸矩形毛坯排樣問題進行求解等[1]。利用VBA技術(shù)結(jié)合Excel的繪圖功能及其ActiveX控件的應用，遞歸算法可以直接通過Excel圖表的動態(tài)模擬展示出來，從而實現(xiàn)算法的求解過程的自動化[2]和可視化。

1 遞歸算法的典型示例

古代印度的貝拿勒斯神廟有一個梵塔，塔內(nèi)有分別標記為A、B、C的3個座，老和尚命令眾和尚將A座上大小不等的64個盤子，借助于B座全部移到C座上。方法是大的總是在下、小的總是在上且每次只能移動一個。上述方法把A座上面的63個盤子搬到B座上，最重、最大的只要搬動1(即264-64)次，而最小的盤子搬動的次數(shù)竟然達9.2×1018(即264-1)次以上，約為所有盤子搬動次數(shù)之和(僅少1次)。這就是著名的Hanoi(漢諾)塔問題。用Excel表格的填充復制功能[3]將漢諾塔的移動次數(shù)在Excel表格中進行模擬計算十分簡單。盤子由大至小的移動次數(shù)分別為：264-64，264-63，……，264-1，64個盤子的總移動次數(shù)分別為21-1，22-1，……，264-1。可以看出，如此移動64個盤子的漢諾塔是一個十分巨大的工程，既使用現(xiàn)代計算機每秒計算1M次移動，也要60萬年。圖1為Excel表格的填充復制功能進行模擬計算漢諾塔的移動次數(shù)。

圖1 Excel表格中漢諾塔的移動次數(shù)模擬計算

漢諾塔問題的計算，是印度古代一道經(jīng)典的數(shù)學題。這種回溯計算方法求解漢諾塔問題到底對不對，利用計算機進行模擬驗證成了計算機程序設計和數(shù)據(jù)結(jié)構(gòu)等課程的經(jīng)典算法——Recursion (遞歸)算法的典型算例。

圖2是僅為5個盤子的漢諾塔移動到27次時的情況。如在一個新建的Excel圖表上利用“剪去同側(cè)角的矩形”繪圖工具繪制五個大小不等的盤子，直線繪制塔座，用藝術(shù)字標記A、B、C。為加強實驗過程的交互性，在圖表上設置兩個名為“開始”和“重置”的按鈕“表單控件”，鏈接VBA過程?！爸刂谩卑粹o的任務是把搬到C座上的盤子搬回A座。 “開始”按鈕即要完成按老和尚方法搬盤子，從A座搬到C座?！伴_始”按鈕所執(zhí)行的VBA過程主要是一個執(zhí)行遞歸程序的語句：n=5: Call HN (n,"A",n,"B",n,"C",n)。

圖2 盤子數(shù)為5的Hanoi(漢諾)塔的模擬

所執(zhí)行的遞歸程序如下：

Sub HN(n,A,An,B,Bn,C,Cn) '遞歸程序

If n = 1 Then'遞歸至“基狀態(tài)”，移動小盤子

ActiveChart.Shapes.Range(Array("剪去同側(cè)角的矩形 13")).Select '選擇小盤子

Top = Cn - An

Selection.ShapeRange.IncrementTop Top * 35

'小盤子往上下移動(Top為正時往上)

If A = "A" Then Left1 = 0: If A = "B" Then Left1 = 200: If A = "C" Then Left1 = 400

If C = "A" Then Left2 = 0: If C = "B" Then Left2 = 200: If C = "C" Then Left2 = 400

Left0 = Left2 - Left1

Selection.ShapeRange.IncrementLeft Left0

'小盤子往左右移動(Left0為正時往右)

ActiveChart.ChartArea.Select

'選擇圖表的空區(qū)域來取消小盤子的選擇狀態(tài)

js = js + 1'給小盤子移動次數(shù)計數(shù)

ActiveChart.Shapes.Range(Array("TextBox 5")).Select

Selection.ShapeRange(1).TextFrame2.TextRange.Characters.Text = js: ActiveChart.ChartArea.Select: DoEvents'將小盤子移動次數(shù)寫入圖1的移動次數(shù)框

For j = 1 To 100000000: Next'循環(huán)延時

Else

Call HN(n-1,A,An-1,C,Cn,B,Bn) '遞歸調(diào)用

If n = 2 Then JX$ = "剪去同側(cè)角的矩形 12": If n = 3 Then JX$ = "剪去同側(cè)角的矩形 11"

If n = 4 Then JX$ = "剪去同側(cè)角的矩形 10": If n = 5 Then JX$ = "剪去同側(cè)角的矩形 9"

ActiveChart.Shapes.Range(Array(JX$)).Select: DoEvents'選擇對應盤子

Top = Cn - An

Selection.ShapeRange.IncrementTop Top * 35

'盤子往上下移動(Top為正時往上)

If A = "A" Then Left1 = 0: If A = "B" Then Left1 = 200: If A = "C" Then Left1 = 400

If C = "A" Then Left2 = 0: If C = "B" Then Left2 = 200: If C = "C" Then Left2 = 400

Left0 = Left2 - Left1

Selection.ShapeRange.IncrementLeft Left0

'盤子往左右移動(Left0為正時往右)

ActiveChart.ChartArea.Select

js = js + 1

ActiveChart.Shapes.Range(Array("TextBox 5")).Select

Selection.ShapeRange(1).TextFrame2.TextRange.Characters.Text = js: ActiveChart.ChartArea.Select

DoEvents '將控制權(quán)還給系統(tǒng)，讓系統(tǒng)顧及其它任務或請求，也使圖形繪制的動態(tài)過程可視化

For j = 1 To 100000000: Next'延時

Call HN(n-1,B,Bn,A,An,C,Cn-1) '遞歸調(diào)用

End If

End Sub

上述算法實驗的動態(tài)模擬是通過VBA程序設計移動繪制好的圖形，產(chǎn)生動畫效果。

2 分形遞歸樹的VBA動態(tài)模擬

分形幾何學廣泛應用于物理、化學、生物等自然科學以及社會科學等領域，計算機上生成分形圖形的算法雖然有迭代、循環(huán)、遞推和遞歸等多種算法，但簡捷、易用的還是遞歸算法。圖3是VBA遞歸算法在Excel中動態(tài)模擬[4]的分形遞歸樹，計算機使分形科學與自然和藝術(shù)完美地融為一體,教學案例得到豐富[5]。繪制分形遞歸樹的遞歸程序如下：

Sub koch(x)

If x = 1 Then

x2 = x1 + d * Cos(JD * 3.14159 / 180)

y2 = y1 + d * Sin(JD * 3.14159 / 180)

ActiveChart.Shapes.AddLine(x1,y1,x2,y2).Select

* 3.14159 / 180): y2 = y1 + d * Sin(JD * 3.14159 / 180) '繪制直線

x1 = x2: y1 = y2

Else

koch (x - 1)：koch (x - 1) '遞歸繪制主枝

xx1 = x1: yy1 = y1：x1 = xx1: y1 = yy1

JD = JD - 20：koch (x - 1)：JD = JD + 10：koch (x - 1)

JD = JD + 15：koch (x - 1) '遞歸繪制左分枝

x1 = xx1: y1 = yy1

JD = JD + 20: koch (x - 1) : JD = JD - 10: koch (x - 1)

JD = JD - 15: koch (x - 1) '遞歸繪制右分枝

x1 = xx1: y1 = yy1

DoEvents'將控制權(quán)還給系統(tǒng)，動態(tài)顯示分形樹的繪制過程。

End If

End Sub

圖3 分形遞歸樹的VBA動態(tài)模擬圖

在插入的Excel圖表中應用VBA繪圖，加入DoEvents語句，動態(tài)模擬效果更為逼真，可以直觀地顯示分形樹的遞歸描繪過程，即由主枝開始，繪完左枝再繪右枝。結(jié)合表單控件功能，交互作用甚為流暢[6]。

分形樹的繪制極大地啟發(fā)了學生對計算機實驗的廣泛興趣，遞歸算法模擬實驗是開拓學生視野、啟迪學生思維較好的計算機實驗題材。Excel中利用VBA遞歸算法模擬的koch分形曲線(圖4)，讓學生體會到自相似結(jié)構(gòu)的計算機遞歸分形圖形具有無窮的藝術(shù)魅力。

圖4 分形遞歸koch曲線的VBA模擬圖

3 結(jié)論

基于Excel平臺的算法模擬實驗，充分利用Excel的函數(shù)功能、重算功能、圖表功能等與VBA混合程序設計，實現(xiàn)了遞歸算法的動態(tài)模擬，通過形象、生動的VBA圖形動畫和VBA自動繪圖，動態(tài)模擬出典型算法發(fā)生、發(fā)展的基本運行過程，使遞歸求解過程結(jié)構(gòu)清晰，可讀性好，易于理解。學生通過動態(tài)模擬實驗獲得對算法的感性認識，加深了對算法實現(xiàn)過程的理解[7]。由于VBA程序與VB程序幾乎相同，利于學生通過遞歸算法的計算機實驗得到程序設計能力的訓練。實踐表明，遞歸算法的VBA動態(tài)模擬實驗適合于計算機經(jīng)典算法的實驗教學。

[1] 李海生.遞歸算法在單一矩形毛坯無約束最優(yōu)排樣中的應用[J].重慶理工大學學報(自然科學),2017,31(9):125-131.

[2] 立濤,阮智,汪玲,等.基于遞歸算法的多級獨立目錄文件上傳技術(shù)的實現(xiàn)[J].現(xiàn)代商貿(mào)工業(yè),2017(15):182-183.

[3] 陳煌,陳錦昌.基于產(chǎn)品基因組的VBA程序建模開發(fā)研究[J].機械設計與制造,2013(1):240-243,247.

[4] BOCTOR D.Microsoft Office 2000 VBA基礎[M].北京超品計算機有限責任公司，譯.北京：人民郵電出版社,2000:187-193.

[5] 朱君波,龔沛曾,楊志強.以計算思維為切入點的遞歸算法教學改革[J].計算機教育,2017(7):30-33，88-90,102.

[6] 顏清,彭小平.基于VBA的動畫模擬課件的設計與實現(xiàn)[J].北京:現(xiàn)代教育技術(shù),2010,20(1)：124-126.

[7] 白秋產(chǎn).基于遞歸算法的最短跳數(shù)路徑的RSS測距算法[J].測控技術(shù),2017,36(6):92-96.

Study of VBA Simulation Experiment of Recursive Algorithm

YAN Qing,MIAO Zhuang,AI Zhihua,LAI Xinsheng

(School of Mathematics and Computer Science，Shangrao Normal University,Shangrao Jiangxi 334001，China)

Use of Excel of drawing function with VBA mixing programming,obtain real-time dynamic simulation algorithm process for the computer experimental results,provides a new solution. The computer simulation experiment of classical algorithm VBA has its unique advantages,students through the simulation experiment,strengthens the algorithm of perceptual knowledge,deepen the understanding of the processes of algorithm. Practice shows that the algorithm based on the classical VBA computer simulation experiment,help students to improve the ability of programming,suitable for computer experiment teaching.

VBA;classical algorithm;computer experiment;simulation

2017-10-23

國家自然科學基金項目(61562071)；江西省教育廳科學技術(shù)研究項目(151063)

顏清(1962-)，女，湖南宜章人，副教授，主要從事計算機應用技術(shù)研究。E-mail:yanq168@126.com

TP391.9

A

1004-2237(2017)06-0020-04

10.3969/j.issn.1004-2237.2017.06.005