郭亞慶

（十堰職業(yè)技術(shù)學(xué)院電子工程系，湖北十堰442000）

在程序設(shè)計(jì)中，遞歸算法一直是教學(xué)的難點(diǎn)，在現(xiàn)階段高職教學(xué)中，傳統(tǒng)的告知式教學(xué)還占有很大的比例。為適應(yīng)學(xué)生的思維結(jié)構(gòu)，幫助學(xué)生構(gòu)建他們能理解的知識(shí)，從而順利理解復(fù)雜的數(shù)學(xué)問題，特制作漢諾塔進(jìn)出棧的動(dòng)態(tài)演示程序，應(yīng)用到VB教學(xué)中，從而把復(fù)雜的教學(xué)問題變?yōu)橹庇^，生動(dòng)的動(dòng)畫教學(xué)，以提高教學(xué)效果。

一、遞歸算法

遞歸算法是一種直接或者間接地調(diào)用自身的算法。它的實(shí)質(zhì)是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)（或過程）來表示問題的解［1］。

遞歸算法清晰簡練、易讀，但要講清楚遞歸的執(zhí)行過程，讓學(xué)生能夠掌握遞歸的實(shí)質(zhì)以及揭示遞歸與堆棧的內(nèi)在聯(lián)系，卻不是一件很容易的事。

堆棧（Stack）是一種比較重要的線性數(shù)據(jù)結(jié)構(gòu)，它的插入、刪除操作是固定在一端進(jìn)行的，這一端稱為棧頂（top），另一端稱為棧底（bottom），向棧中插入數(shù)據(jù)的操作稱為壓棧（Push），從棧中刪除數(shù)據(jù)稱為彈出（Pop）。在計(jì)算機(jī)中正是由于有了堆棧這種數(shù)據(jù)結(jié)構(gòu)，才使遞歸算法得以實(shí)現(xiàn)。

二、遞歸過程執(zhí)行分析

下面我們以Hanoi塔問題為例，相傳在印度，有一個(gè)梵塔，塔內(nèi)有三根柱子A、B、C，A柱上有64個(gè)盤子，盤子大小不等，大的在下，小的在上，有一個(gè)和尚想把這64個(gè)盤子從A柱移到C柱，但每次只能允許移動(dòng)一個(gè)盤子，并且在移動(dòng)過程中，要求3個(gè)柱上的盤子始終保持大盤在下，小盤在上。

我們將三根柱子分別標(biāo)號(hào)為A、B、C，目的是要將n個(gè)盤子從A柱子移動(dòng)到C柱子。該問題的算法如下：第一步將A柱子上n－1個(gè)盤子借助C柱子移動(dòng)到B柱子上；第二步 將A柱子上剩余的第n個(gè)盤子移動(dòng)到C柱子上；第三步 將B柱子上的n－1個(gè)盤子借助A柱子移動(dòng)到C柱子上［2］。

對(duì)于第一步和第三步，我們又可以利用類似的方法繼續(xù)將其求解過程設(shè)計(jì)為一個(gè)規(guī)模為n－1的Hanoi塔遞歸算法。

遞歸過程的實(shí)質(zhì)是循環(huán)執(zhí)行遞歸過程中遞歸調(diào)用語句前的幾個(gè)語句，每次執(zhí)行遞歸調(diào)用語句時(shí)將返回地址及實(shí)參的值進(jìn)棧保留，調(diào)用時(shí)注意形參與實(shí)參的結(jié)合。若是變參不在重新分配內(nèi)存單元，若是值參（如本例中的N，A，B，C）每調(diào)用一次都給N，A，B，C變量重新分配內(nèi)存單元，登記該變量在本層的實(shí)際值，當(dāng)我們單擊按鈕2時(shí)，便開始調(diào)用遞歸程序，實(shí)參N（設(shè)N＝3），1，2，3分別傳送給形參N，A，B，C。這時(shí)返回地址FH及N，A，B，C對(duì)應(yīng)的實(shí)參值進(jìn)棧，當(dāng)N不為1時(shí)，用30語句hanoi N－1，A，C，B（實(shí)際用2，1，3，2）再調(diào)用，N又不為1，再用30語句hanoi N－1，A，C，B（實(shí)際用1，1，2，3）調(diào)用，直到滿足N＝1時(shí)，則執(zhí)行20語句：A－＞C，這時(shí)對(duì)初學(xué)者來說往往找不到A，C的實(shí)際值，而無法寫出源柱和目標(biāo)柱。即使執(zhí)行完20語句后，又因找不到返回地址而感到茫然，靠一步步推算，寫出進(jìn)出棧參數(shù)及返回地址，即費(fèi)時(shí)又易出錯(cuò)，當(dāng)N值大于3時(shí)，推算更為困難。為此本人開發(fā)了漢諾塔問題進(jìn)出棧動(dòng)態(tài)演示程序，它生動(dòng)而直觀顯示了進(jìn)出棧參數(shù)及返回地址，記錄了棧內(nèi)參數(shù)的變化，根據(jù)棧頂?shù)膮?shù)，很方便地寫出“A－＞C”。從而加深了學(xué)生對(duì)遞歸過程執(zhí)行的理解。

三、進(jìn)出棧動(dòng)態(tài)演示程序的設(shè)計(jì)

1.界面設(shè)計(jì)

在屏幕左半部上畫出棧圖，棧圖上方有五個(gè)文本框，標(biāo)示為ADR（返回地址）N，A，B，C以表示進(jìn)棧的參數(shù)。在棧底左側(cè)畫出棧指針，棧指針是先作一個(gè)框架，然后在框架內(nèi)放入一個(gè)標(biāo)簽框，一個(gè)文本框和箭頭，其中文本框是用于存放棧頂?shù)牡刂?，初始指向棧底。屏幕的右半部上方有一個(gè)文本框用于提示執(zhí)行情況。屏幕的右半部的中間為輸出結(jié)果，下部為三個(gè)按鈕。

2.初始化

先輸入園盤個(gè)數(shù)N，由于屏幕關(guān)系，園盤個(gè)數(shù)僅限于3和4，然后根據(jù)園盤個(gè)數(shù)在屏幕的右半部產(chǎn)生7或15個(gè)標(biāo)簽框用于顯示輸出結(jié)果，再產(chǎn)生8行5列的文本框填入棧圖作為?？臻g，并將它們的Visible屬性設(shè)為False。

3.進(jìn)出棧時(shí)間的安排

在什么時(shí)候進(jìn)棧，什么時(shí)候出棧這是進(jìn)出棧的動(dòng)態(tài)演示程序設(shè)計(jì)的關(guān)鍵，我們知道每當(dāng)調(diào)用子程序時(shí)，就必須將返回地址及相應(yīng)參數(shù)壓棧，為此我們?cè)谏鲜鏊惴ǖ娜幉迦肓苏{(diào)用進(jìn)棧子程序，并且用窗體級(jí)變量X來統(tǒng)計(jì)棧內(nèi)的項(xiàng)數(shù)，每當(dāng)進(jìn)棧X就加1，每當(dāng)退棧X就減1。進(jìn)而分析可知，一旦滿足條件N＝1時(shí)，就會(huì)執(zhí)行20顯示輸出結(jié)果，執(zhí)行完20語句之后，就會(huì)退出塊IF語句，而執(zhí)行60END SUB語句，這時(shí)就從棧頂彈出一項(xiàng)。因而將退棧子程序插入在60語句之前。另外為正確顯示輸出結(jié)果，用變量T來控制LAB（T）.Caption的下標(biāo)，因而在20與40語句之前插入T＝T＋1語句。改進(jìn)后的算法如下。

4.進(jìn)棧與出棧子程序的設(shè)計(jì)

（1）進(jìn)棧子程序：?？臻g是用TXTNEW的二維數(shù)組表示，它是8行5列，每個(gè)元素的類型為TEXTBOX，一行存放一次進(jìn)棧的所有參數(shù)，它們分別是返回地址和N，A，B，C。進(jìn)棧子程序JZ有6個(gè)形參，其中形參X為地址傳遞，用來控制TXTNEW二維數(shù)組的行下標(biāo)，以統(tǒng)計(jì)棧內(nèi)的項(xiàng)數(shù)，每當(dāng)調(diào)用進(jìn)棧子程序X就加1。其余5個(gè)形參分別對(duì)應(yīng)返回地址和N，A，B，C，進(jìn)棧子程序是先將棧指針上移，接著將棧指針內(nèi)存放的棧頂?shù)刂窚p1，然后將返回地址和N，A，B，C這些參數(shù)存入二維數(shù)組TXTNEW的X行各列中，并顯示該行，以表示進(jìn)棧。

（2）退棧子程序：它有一個(gè)形參X用來控制TXTNEW二維數(shù)組的行下標(biāo)，將該行各列的Visible屬性設(shè)為FALSE，接著棧指針下移，然后將棧指針內(nèi)存放的棧頂?shù)刂芳?，每當(dāng)調(diào)用退棧子程序X就減1。

附進(jìn)出棧子程序如下：

［1］劉瑞新.VISUAL BASIC程序設(shè)計(jì)教程［M］.北京：電子工業(yè)出版社，2011：162.

［2］譚浩強(qiáng).C程序設(shè)計(jì)［M］.北京：清華大學(xué)出版社，2010：118－119.