递归执行过程中进出栈的动态演示在VB教学中的应用

2012-01-20 06:49郭亚庆
湖北工业职业技术学院学报 2012年1期
关键词:文本框柱子子程序

郭亚庆

(十堰职业技术学院电子工程系,湖北十堰442000)

在程序设计中,递归算法一直是教学的难点,在现阶段高职教学中,传统的告知式教学还占有很大的比例。为适应学生的思维结构,帮助学生构建他们能理解的知识,从而顺利理解复杂的数学问题,特制作汉诺塔进出栈的动态演示程序,应用到VB教学中,从而把复杂的教学问题变为直观,生动的动画教学,以提高教学效果。

一、递归算法

递归算法是一种直接或者间接地调用自身的算法。它的实质是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解[1]。

递归算法清晰简练、易读,但要讲清楚递归的执行过程,让学生能够掌握递归的实质以及揭示递归与堆栈的内在联系,却不是一件很容易的事。

堆栈(Stack)是一种比较重要的线性数据结构,它的插入、删除操作是固定在一端进行的,这一端称为栈顶(top),另一端称为栈底(bottom),向栈中插入数据的操作称为压栈(Push),从栈中删除数据称为弹出(Pop)。在计算机中正是由于有了堆栈这种数据结构,才使递归算法得以实现。

二、递归过程执行分析

下面我们以Hanoi塔问题为例,相传在印度,有一个梵塔,塔内有三根柱子A、B、C,A柱上有64个盘子,盘子大小不等,大的在下,小的在上,有一个和尚想把这64个盘子从A柱移到C柱,但每次只能允许移动一个盘子,并且在移动过程中,要求3个柱上的盘子始终保持大盘在下,小盘在上。

我们将三根柱子分别标号为A、B、C,目的是要将n个盘子从A柱子移动到C柱子。该问题的算法如下:第一步将A柱子上n-1个盘子借助C柱子移动到B柱子上;第二步 将A柱子上剩余的第n个盘子移动到C柱子上;第三步 将B柱子上的n-1个盘子借助A柱子移动到C柱子上[2]。

对于第一步和第三步,我们又可以利用类似的方法继续将其求解过程设计为一个规模为n-1的Hanoi塔递归算法。

递归过程的实质是循环执行递归过程中递归调用语句前的几个语句,每次执行递归调用语句时将返回地址及实参的值进栈保留,调用时注意形参与实参的结合。若是变参不在重新分配内存单元,若是值参(如本例中的N,A,B,C)每调用一次都给N,A,B,C变量重新分配内存单元,登记该变量在本层的实际值,当我们单击按钮2时,便开始调用递归程序,实参N(设N=3),1,2,3分别传送给形参N,A,B,C。这时返回地址FH及N,A,B,C对应的实参值进栈,当N不为1时,用30语句hanoi N-1,A,C,B(实际用2,1,3,2)再调用,N又不为1,再用30语句hanoi N-1,A,C,B(实际用1,1,2,3)调用,直到满足N=1时,则执行20语句:A->C,这时对初学者来说往往找不到A,C的实际值,而无法写出源柱和目标柱。即使执行完20语句后,又因找不到返回地址而感到茫然,靠一步步推算,写出进出栈参数及返回地址,即费时又易出错,当N值大于3时,推算更为困难。为此本人开发了汉诺塔问题进出栈动态演示程序,它生动而直观显示了进出栈参数及返回地址,记录了栈内参数的变化,根据栈顶的参数,很方便地写出“A->C”。从而加深了学生对递归过程执行的理解。

三、进出栈动态演示程序的设计

1.界面设计

在屏幕左半部上画出栈图,栈图上方有五个文本框,标示为ADR(返回地址)N,A,B,C以表示进栈的参数。在栈底左侧画出栈指针,栈指针是先作一个框架,然后在框架内放入一个标签框,一个文本框和箭头,其中文本框是用于存放栈顶的地址,初始指向栈底。屏幕的右半部上方有一个文本框用于提示执行情况。屏幕的右半部的中间为输出结果,下部为三个按钮。

2.初始化

先输入园盘个数N,由于屏幕关系,园盘个数仅限于3和4,然后根据园盘个数在屏幕的右半部产生7或15个标签框用于显示输出结果,再产生8行5列的文本框填入栈图作为栈空间,并将它们的Visible属性设为False。

3.进出栈时间的安排

在什么时候进栈,什么时候出栈这是进出栈的动态演示程序设计的关键,我们知道每当调用子程序时,就必须将返回地址及相应参数压栈,为此我们在上述算法的三处插入了调用进栈子程序,并且用窗体级变量X来统计栈内的项数,每当进栈X就加1,每当退栈X就减1。进而分析可知,一旦满足条件N=1时,就会执行20显示输出结果,执行完20语句之后,就会退出块IF语句,而执行60END SUB语句,这时就从栈顶弹出一项。因而将退栈子程序插入在60语句之前。另外为正确显示输出结果,用变量T来控制LAB(T).Caption的下标,因而在20与40语句之前插入T=T+1语句。改进后的算法如下。

4.进栈与出栈子程序的设计

(1)进栈子程序:栈空间是用TXTNEW的二维数组表示,它是8行5列,每个元素的类型为TEXTBOX,一行存放一次进栈的所有参数,它们分别是返回地址和N,A,B,C。进栈子程序JZ有6个形参,其中形参X为地址传递,用来控制TXTNEW二维数组的行下标,以统计栈内的项数,每当调用进栈子程序X就加1。其余5个形参分别对应返回地址和N,A,B,C,进栈子程序是先将栈指针上移,接着将栈指针内存放的栈顶地址减1,然后将返回地址和N,A,B,C这些参数存入二维数组TXTNEW的X行各列中,并显示该行,以表示进栈。

(2)退栈子程序:它有一个形参X用来控制TXTNEW二维数组的行下标,将该行各列的Visible属性设为FALSE,接着栈指针下移,然后将栈指针内存放的栈顶地址加1,每当调用退栈子程序X就减1。

附进出栈子程序如下:

[1]刘瑞新.VISUAL BASIC程序设计教程[M].北京:电子工业出版社,2011:162.

[2]谭浩强.C程序设计[M].北京:清华大学出版社,2010:118-119.

猜你喜欢
文本框柱子子程序
城里有朋友
希腊遗址
巧用文本框实现PPT多图片排版
观察:长廊和柱子
PPT文本框的另类应用
浅谈子程序在数控车编程中的应用
文本框酷变3D效果
子程序在数控车加工槽中的应用探索
西门子840D系统JOG模式下PLC调用并执行NC程序
简化编程与子程序嵌套的应用