遞歸算法的VBA模擬實(shí)驗(yàn)研究

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

遞歸算法的VBA模擬實(shí)驗(yàn)研究

顏清，苗壯，艾志華，賴(lài)鑫生

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

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

VBA；經(jīng)典算法；計(jì)算機(jī)實(shí)驗(yàn)；模擬

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

1 遞歸算法的典型示例

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

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

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

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

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

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

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

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

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

Top = Cn - An

Selection.ShapeRange.IncrementTop Top * 35

'小盤(pán)子往上下移動(dòng)(Top為正時(shí)往上)

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

'小盤(pán)子往左右移動(dòng)(Left0為正時(shí)往右)

ActiveChart.ChartArea.Select

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

js = js + 1'給小盤(pán)子移動(dòng)次數(shù)計(jì)數(shù)

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

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

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

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'選擇對(duì)應(yīng)盤(pán)子

Top = Cn - An

Selection.ShapeRange.IncrementTop Top * 35

'盤(pán)子往上下移動(dòng)(Top為正時(shí)往上)

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

'盤(pán)子往左右移動(dòng)(Left0為正時(shí)往右)

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)顧及其它任務(wù)或請(qǐng)求，也使圖形繪制的動(dòng)態(tài)過(guò)程可視化

For j = 1 To 100000000: Next'延時(shí)

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

End If

End Sub

上述算法實(shí)驗(yàn)的動(dòng)態(tài)模擬是通過(guò)VBA程序設(shè)計(jì)移動(dòng)繪制好的圖形，產(chǎn)生動(dòng)畫(huà)效果。

2 分形遞歸樹(shù)的VBA動(dòng)態(tài)模擬

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

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)，動(dòng)態(tài)顯示分形樹(shù)的繪制過(guò)程。

End If

End Sub

圖3 分形遞歸樹(shù)的VBA動(dòng)態(tài)模擬圖

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

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

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

3 結(jié)論

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

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

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

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

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

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

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

[7] 白秋產(chǎn).基于遞歸算法的最短跳數(shù)路徑的RSS測(cè)距算法[J].測(cè)控技術(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

國(guó)家自然科學(xué)基金項(xiàng)目(61562071)；江西省教育廳科學(xué)技術(shù)研究項(xiàng)目(151063)

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

TP391.9

A

1004-2237(2017)06-0020-04

10.3969/j.issn.1004-2237.2017.06.005