递归算法的VBA模拟实验研究
2017-12-22
(上饶师范学院 数学与计算机科学学院，江西 上饶 334001)
递归算法的VBA模拟实验研究
颜清，苗壮，艾志华，赖鑫生
(上饶师范学院 数学与计算机科学学院，江西 上饶 334001)
利用Excel的绘图功能与VBA混合程序设计，获得算法过程的实时动态模拟效果，为计算机实验提供了一个崭新的解决方案。计算机经典算法的VBA模拟实验有其独特的优点，学生通过模拟实验，增强了对算法的感性认识，加深了对算法实现过程的理解。实践表明，基于VBA的计算机经典算法模拟实验，有利于学生的程序设计能力的提高，适合于计算机实验教学。
VBA；经典算法；计算机实验；模拟
递归算法是计算机经典算法之一，递归算法是一个不断循环自我调用的过程，即指函数或过程或程序直接或间接调用自身的现象，对某些复杂的计算十分有效。作为循环调用的出口,递归算法首先要有一个确切的初始值，即所谓的“基状态”。若以参数n表示问题的复杂度，n的“基状态”常选择1或0，然后就可进入递归算法的关键过程——递归调用。递归调用过程分为递推和回归两个阶段。递推阶段将参数复杂度由n降低为n-1，是一个复杂度降低的过程，参数n最终向复杂度1的“基状态”逼近而终止；回归阶段是由“基状态”的确切解逐级返回的过程，由“基状态”依次获取参数的复杂度递增至n的解为止。在工程应用中，应用参数n的地方十分常见，如重庆大学李海生利用递归算法对单一尺寸矩形毛坯排样问题进行求解等[1]。利用VBA技术结合Excel的绘图功能及其ActiveX控件的应用，递归算法可以直接通过Excel图表的动态模拟展示出来，从而实现算法的求解过程的自动化[2]和可视化。
1 递归算法的典型示例
古代印度的贝拿勒斯神庙有一个梵塔，塔内有分别标记为A、B、C的3个座，老和尚命令众和尚将A座上大小不等的64个盘子，借助于B座全部移到C座上。方法是大的总是在下、小的总是在上且每次只能移动一个。上述方法把A座上面的63个盘子搬到B座上，最重、最大的只要搬动1(即264-64)次，而最小的盘子搬动的次数竟然达9.2×1018(即264-1)次以上，约为所有盘子搬动次数之和(仅少1次)。这就是著名的Hanoi(汉诺)塔问题。用Excel表格的填充复制功能[3]将汉诺塔的移动次数在Excel表格中进行模拟计算十分简单。盘子由大至小的移动次数分别为：264-64，264-63，……，264-1，64个盘子的总移动次数分别为21-1，22-1，……，264-1。可以看出，如此移动64个盘子的汉诺塔是一个十分巨大的工程，既使用现代计算机每秒计算1M次移动，也要60万年。图1为Excel表格的填充复制功能进行模拟计算汉诺塔的移动次数。
图1 Excel表格中汉诺塔的移动次数模拟计算
汉诺塔问题的计算，是印度古代一道经典的数学题。这种回溯计算方法求解汉诺塔问题到底对不对，利用计算机进行模拟验证成了计算机程序设计和数据结构等课程的经典算法——Recursion (递归)算法的典型算例。
图2是仅为5个盘子的汉诺塔移动到27次时的情况。如在一个新建的Excel图表上利用“剪去同侧角的矩形”绘图工具绘制五个大小不等的盘子，直线绘制塔座，用艺术字标记A、B、C。为加强实验过程的交互性，在图表上设置两个名为“开始”和“重置”的按钮“表单控件”，链接VBA过程。“重置”按钮的任务是把搬到C座上的盘子搬回A座。 “开始”按钮即要完成按老和尚方法搬盘子，从A座搬到C座。“开始”按钮所执行的VBA过程主要是一个执行递归程序的语句：n=5: Call HN (n,"A",n,"B",n,"C",n)。
图2 盘子数为5的Hanoi(汉诺)塔的模拟
所执行的递归程序如下：
Sub HN(n,A,An,B,Bn,C,Cn) '递归程序
If n = 1 Then'递归至“基状态”，移动小盘子
ActiveChart.Shapes.Range(Array("剪去同侧角的矩形 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
'选择图表的空区域来取消小盘子的选择状态
js = js + 1'给小盘子移动次数计数
ActiveChart.Shapes.Range(Array("TextBox 5")).Select
Selection.ShapeRange(1).TextFrame2.TextRange.Characters.Text = js: ActiveChart.ChartArea.Select: DoEvents'将小盘子移动次数写入图1的移动次数框
For j = 1 To 100000000: Next'循环延时
Else
Call HN(n-1,A,An-1,C,Cn,B,Bn) '递归调用
If n = 2 Then JX$ = "剪去同侧角的矩形 12": If n = 3 Then JX$ = "剪去同侧角的矩形 11"
If n = 4 Then JX$ = "剪去同侧角的矩形 10": If n = 5 Then JX$ = "剪去同侧角的矩形 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 '将控制权还给系统，让系统顾及其它任务或请求，也使图形绘制的动态过程可视化
For j = 1 To 100000000: Next'延时
Call HN(n-1,B,Bn,A,An,C,Cn-1) '递归调用
End If
End Sub
上述算法实验的动态模拟是通过VBA程序设计移动绘制好的图形，产生动画效果。
2 分形递归树的VBA动态模拟
分形几何学广泛应用于物理、化学、生物等自然科学以及社会科学等领域，计算机上生成分形图形的算法虽然有迭代、循环、递推和递归等多种算法，但简捷、易用的还是递归算法。图3是VBA递归算法在Excel中动态模拟[4]的分形递归树，计算机使分形科学与自然和艺术完美地融为一体,教学案例得到丰富[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'将控制权还给系统，动态显示分形树的绘制过程。
End If
End Sub
图3 分形递归树的VBA动态模拟图
在插入的Excel图表中应用VBA绘图，加入DoEvents语句，动态模拟效果更为逼真，可以直观地显示分形树的递归描绘过程，即由主枝开始，绘完左枝再绘右枝。结合表单控件功能，交互作用甚为流畅[6]。
分形树的绘制极大地启发了学生对计算机实验的广泛兴趣，递归算法模拟实验是开拓学生视野、启迪学生思维较好的计算机实验题材。Excel中利用VBA递归算法模拟的koch分形曲线(图4)，让学生体会到自相似结构的计算机递归分形图形具有无穷的艺术魅力。
图4 分形递归koch曲线的VBA模拟图
3 结论
基于Excel平台的算法模拟实验，充分利用Excel的函数功能、重算功能、图表功能等与VBA混合程序设计，实现了递归算法的动态模拟，通过形象、生动的VBA图形动画和VBA自动绘图，动态模拟出典型算法发生、发展的基本运行过程，使递归求解过程结构清晰，可读性好，易于理解。学生通过动态模拟实验获得对算法的感性认识，加深了对算法实现过程的理解[7]。由于VBA程序与VB程序几乎相同，利于学生通过递归算法的计算机实验得到程序设计能力的训练。实践表明，递归算法的VBA动态模拟实验适合于计算机经典算法的实验教学。
[1] 李海生.递归算法在单一矩形毛坯无约束最优排样中的应用[J].重庆理工大学学报(自然科学),2017,31(9):125-131.
[2] 立涛,阮智,汪玲,等.基于递归算法的多级独立目录文件上传技术的实现[J].现代商贸工业,2017(15):182-183.
[3] 陈煌,陈锦昌.基于产品基因组的VBA程序建模开发研究[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的动画模拟课件的设计与实现[J].北京:现代教育技术,2010,20(1)：124-126.
[7] 白秋产.基于递归算法的最短跳数路径的RSS测距算法[J].测控技术,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)；江西省教育厅科学技术研究项目(151063)
颜清(1962-)，女，湖南宜章人，副教授，主要从事计算机应用技术研究。E-mail:yanq168@126.com
TP391.9
A
1004-2237(2017)06-0020-04
10.3969/j.issn.1004-2237.2017.06.005
