算法驅(qū)動(dòng)的面向?qū)ο蟪绦蛟O(shè)計(jì)教學(xué)研究

摘要：本文根據(jù)“研究型”教學(xué)的要求，分析了程序設(shè)計(jì)相關(guān)課程之間的連續(xù)性與層次性，探討了面向?qū)ο蟪绦蛟O(shè)計(jì)教學(xué)過程與算法及數(shù)據(jù)結(jié)構(gòu)的關(guān)聯(lián)，提出了算法驅(qū)動(dòng)的、面向設(shè)計(jì)的教學(xué)模式并給出了應(yīng)用實(shí)例。

關(guān)鍵詞：面向?qū)ο?；層次性；關(guān)聯(lián)性；教學(xué)模式

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：A

1引言

面向?qū)ο蟪绦蛟O(shè)計(jì)技術(shù)是當(dāng)前軟件開發(fā)的主流技術(shù)。因此該課程是計(jì)算機(jī)專業(yè)的十分重要的專業(yè)課程。它是學(xué)生進(jìn)一步學(xué)習(xí)可視化編程及理解組件編程的基礎(chǔ)，同時(shí)也是計(jì)算機(jī)實(shí)踐應(yīng)用及對(duì)學(xué)生進(jìn)行創(chuàng)新能力培養(yǎng)的基礎(chǔ)之一。

顯然，在實(shí)際授課中，我們不能片面從語(yǔ)法、語(yǔ)句及理論概念的角度去教授該課程，而應(yīng)該是面向問題與應(yīng)用的、構(gòu)建于相關(guān)知識(shí)體系上的研究型教學(xué)。所謂“研究型教學(xué)”，就是要利用知識(shí)的載體屬性，即以知識(shí)為載體，通過知識(shí)點(diǎn)、知識(shí)的發(fā)現(xiàn)過程、知識(shí)的創(chuàng)建過程，讓學(xué)生學(xué)會(huì)思維，學(xué)會(huì)用科學(xué)的方法分析、解決問題。在這里，我們強(qiáng)調(diào)的是學(xué)生“學(xué)會(huì)”，是學(xué)生作為一個(gè)教學(xué)中的主體“學(xué)會(huì)”。其基礎(chǔ)必須以足夠的相關(guān)知識(shí)作為載體，以體系化的知識(shí)為學(xué)習(xí)場(chǎng)景。對(duì)于面向?qū)ο蟪绦蛟O(shè)計(jì)，如果從“研究型”教學(xué)的要求出發(fā)，應(yīng)該以算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)思想、計(jì)算機(jī)語(yǔ)言等相關(guān)知識(shí)為載體，從綜合的、體系化的角度去理解面向?qū)ο蟮膬?nèi)涵，在這里算法是程序設(shè)計(jì)的核心。正如一些著名計(jì)算機(jī)科學(xué)家在有關(guān)計(jì)算機(jī)科學(xué)教育的論述中認(rèn)為，計(jì)算機(jī)科學(xué)是一種創(chuàng)造性的思維活動(dòng)，計(jì)算機(jī)科學(xué)的核心問題是算法理論，其教育必須面向設(shè)計(jì)[1]。因此，如果將面向?qū)ο蟮某绦蛟O(shè)計(jì)教學(xué)過程“嵌入”到算法的設(shè)計(jì)過程中，以算法為主線，以問題為導(dǎo)向去理解面向?qū)ο蠹夹g(shù)的理論與方法，將學(xué)習(xí)與“消化”過程有機(jī)的結(jié)合起來，能夠從根本上提高學(xué)生綜合分析能力及繼續(xù)學(xué)習(xí)的能力。

2目前教學(xué)過程中存在的一些問題

在教學(xué)方法上，側(cè)重于對(duì)面向?qū)ο笙嚓P(guān)術(shù)語(yǔ)及概念的灌輸，不能很好地與結(jié)構(gòu)化編程的思想進(jìn)行對(duì)比學(xué)習(xí)。側(cè)重于對(duì)語(yǔ)法、語(yǔ)義、語(yǔ)用環(huán)境的理解與學(xué)習(xí)，是以概念理解和記憶為主要手段的繼承式學(xué)習(xí)，這樣做的結(jié)果是學(xué)生僅僅在很淺的層次上學(xué)習(xí)了一種編程的方法及一些簡(jiǎn)單語(yǔ)法規(guī)范，相對(duì)于非計(jì)算機(jī)專業(yè)學(xué)生的程序設(shè)計(jì)學(xué)習(xí)來說，體現(xiàn)不出計(jì)算機(jī)專業(yè)的優(yōu)勢(shì)。

在教學(xué)內(nèi)容的組織上，片面強(qiáng)調(diào)教學(xué)進(jìn)度與信息量等外在的東西，忽視對(duì)學(xué)生分析與解決問題能力的引導(dǎo)，各門相關(guān)課程之間缺少銜接，不能很好的將編程環(huán)境、程序設(shè)計(jì)語(yǔ)言、算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)思想關(guān)聯(lián)起來形成體系化教學(xué)?？傊?，無論是從教學(xué)內(nèi)容、方法及手段上看，與“研究型教學(xué)”的要求相去甚遠(yuǎn)。

3算法驅(qū)動(dòng)的教學(xué)過程的設(shè)計(jì)

教學(xué)的總體構(gòu)想是充分利用面向?qū)ο蟪绦蛟O(shè)計(jì)的“實(shí)踐”，用于解決算法中的“理論”問題，以此來學(xué)習(xí)、理解和應(yīng)用面向?qū)ο蟪绦蛟O(shè)計(jì)的思想及語(yǔ)法規(guī)范。以學(xué)生為主體，在知識(shí)體系上形成一個(gè)完整的、立體的對(duì)面向?qū)ο蟪绦蛟O(shè)計(jì)思想及過程的理解。

具體可以表示為按照計(jì)算機(jī)解決實(shí)際問題的基本流程來設(shè)計(jì)教學(xué)過程，表示如下：

(1) 提出問題

問題的選擇最好能涉及到經(jīng)典的算法范例，把算法思想通過實(shí)例形象地表達(dá)出來。問題的選擇至少應(yīng)滿足一些要求。首先問題建模要符合學(xué)生當(dāng)前的知識(shí)掌握程度，這里主要說的是相關(guān)的數(shù)學(xué)知識(shí)。其次問題所涉及的的算法與程序代碼應(yīng)符合由淺入深、由簡(jiǎn)入繁的認(rèn)知規(guī)律，特別需要強(qiáng)調(diào)的是在初級(jí)階段，對(duì)算法只是一種理念的引入，因此要盡量簡(jiǎn)單一些。再次，問題應(yīng)具有典型性和啟發(fā)性，最好能夠涉及到計(jì)算機(jī)解決問題的全過程。

假設(shè)我們想通過回溯算法來組織面向?qū)ο蟪绦蛟O(shè)計(jì)的教學(xué)過程，可引入如下典型的“n皇后”問題：

問題描述：在n×n格的棋盤上放置彼此不受攻擊的n個(gè)皇后，按照國(guó)際象棋的規(guī)則，皇后可以攻擊在同一行或同一列或同一斜線上的棋子。設(shè)計(jì)程序使得在n×n格的棋盤上放置n個(gè)皇后，任何兩個(gè)皇后不放在同一行或同一列或同一斜線上。

(2) 對(duì)問題建立模型

問題提出后，如何用數(shù)學(xué)模型來描述實(shí)際問題是程序設(shè)計(jì)的起點(diǎn)。由實(shí)際問題抽象出數(shù)學(xué)模型進(jìn)而設(shè)計(jì)出計(jì)算機(jī)表示的數(shù)據(jù)結(jié)構(gòu)是培養(yǎng)學(xué)生抽象能力的重要環(huán)節(jié)。抽象能力是計(jì)算機(jī)專業(yè)工作者的基本素質(zhì)，抽象的層次越高，想象的維數(shù)就越多。由于我們的教學(xué)重點(diǎn)在于面向?qū)ο蟪绦蛟O(shè)計(jì)方法的教學(xué)，此環(huán)節(jié)的作用在于讓學(xué)生體驗(yàn)用計(jì)算機(jī)解決問題的綜合性，因此所提出的問題建立模型較簡(jiǎn)單。當(dāng)然隨著學(xué)生學(xué)習(xí)的深入，應(yīng)該逐漸強(qiáng)調(diào)數(shù)學(xué)建模的訓(xùn)練。

對(duì)于上述范例，不同的學(xué)生可能提出不同的建模方案，教師應(yīng)對(duì)學(xué)生的方案進(jìn)行分析總結(jié)并將自己的抽象過程講解給學(xué)生。可以采用如下簡(jiǎn)單模型：

1) 輸入：

n (n為大于0的整數(shù)，所表示的意義為棋盤的大小及皇后的多少)

2) 限界條件(滿足題目所要求的棋子擺放的條件)：

上式中xi 表示第i行的列位置。

3) 輸出

{y1 y2y3 … yn }

yi 為第i行的棋子所在的列。

(3)算法設(shè)計(jì)

算法的設(shè)計(jì)是在數(shù)學(xué)模型基礎(chǔ)上，對(duì)學(xué)生創(chuàng)造力和想象力的進(jìn)一步培養(yǎng)，是解決問題的核心所在。無論什么樣的程序設(shè)計(jì)思想方法、數(shù)學(xué)模型、程序代碼都是為算法服務(wù)的，以算法為核心的程序設(shè)計(jì)才有現(xiàn)實(shí)意義，進(jìn)而能使學(xué)生深刻理解程序設(shè)計(jì)思想。就一個(gè)實(shí)際問題，在算法設(shè)計(jì)這一環(huán)節(jié)中要充分發(fā)揮學(xué)生的觀察力、想象力，爭(zhēng)取每個(gè)學(xué)生都能提出自己的解決方案(至少應(yīng)能提出一種設(shè)計(jì)思想)。教師也可以在此基礎(chǔ)上與學(xué)生共同討論提出自己的算法，不能強(qiáng)迫學(xué)生接受自己的思想，而是要鼓勵(lì)他們通過自己的分析來判斷哪種方案更適合。提出的算法是要借助于某種語(yǔ)言來描述出來，這些語(yǔ)言可以是自然語(yǔ)言、數(shù)學(xué)語(yǔ)言或約定的符號(hào)語(yǔ)言。

我們采取回溯法解決上述范例可以用偽C描述其算法：

N_QUEEN(n)//n皇后問題算法

x[1]=0，k=1 //x[k]表示第k行皇后的列位置

while k>0

do x[k]=x[k]+1 //逐行擺放

whilex[k]= =n PLACE(k，x[k])= =1//不符合擺放條件

do x[k]=x[k]+1，

if x[k]<=n// 說明在未到n之前找到了能放的位置

then if k==n //說明全部解都求出來了

then output x//輸出結(jié)果

else push(x[k])，k=k+1，x[k]=0 //將結(jié)果壓棧，繼續(xù)下一行

else k=k-1;pop() //如果所有列都試過了還沒解，則回溯，將結(jié)果出棧

PLACE(k，x[k])為按照限界條件判斷是否在指定的行列上擺放棋子。顯然在此算法中需要用到一個(gè)稱為“堆?！钡臄?shù)據(jù)結(jié)構(gòu)。它能夠保存必要的數(shù)據(jù)，同時(shí)能提供保存狀態(tài)與恢復(fù)前一狀態(tài)的功能。應(yīng)該是集數(shù)據(jù)與操作的封裝體，它能夠作為一個(gè)整體為算法的實(shí)現(xiàn)提供服務(wù)。

(4) 抽象數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)

抽象數(shù)據(jù)類型(Abstract Data Type)是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。它是對(duì)數(shù)據(jù)結(jié)構(gòu)更高的抽象。通過抽象數(shù)據(jù)類型來進(jìn)一步引入類與對(duì)象的設(shè)計(jì)，抽象數(shù)據(jù)類型可以對(duì)面向?qū)ο蟪绦蛟O(shè)計(jì)中的類與對(duì)象進(jìn)行更深刻的理解。

針對(duì)本例中所需的是一個(gè)關(guān)于堆棧的抽象數(shù)據(jù)類型，描述為：

ADT Stack{

數(shù)據(jù)部分：

數(shù)據(jù)對(duì)象：D={ ai| ai∈ElemSet， i=0，1，2，…，n，n>=0}

數(shù)據(jù)關(guān)系：Rl={〈ai-1， ai 〉| ai-1， ai ∈D，i=0，1，2，…，n }

a0為棧頂元素，an為棧底元素

操作部分：

InitStack(S)//構(gòu)造一個(gè)空棧S

DestroyStack(S)//銷毀棧S

ClearStack(S)//將堆棧置空

StackEmpty(S)//判斷是否為空棧

StackFull(S)//判斷是否棧滿(只用于順序棧的操作中)

GetStackLength(L)//得到棧的長(zhǎng)度

Push(e)//將e壓棧

Pop(e)//獲得棧頂元素至e中，并從堆棧中刪除棧頂元素

}ADT Stack

在此抽象數(shù)據(jù)類型中，需要定義數(shù)據(jù)元素和數(shù)據(jù)關(guān)系，由此產(chǎn)生實(shí)際的數(shù)據(jù)結(jié)構(gòu)，本例中的教學(xué)，在初級(jí)階段應(yīng)該引導(dǎo)學(xué)生采用簡(jiǎn)單的結(jié)構(gòu)體來描述數(shù)據(jù)項(xiàng)和數(shù)據(jù)元素，甚至直接采用基本數(shù)據(jù)類型及數(shù)組來描述。然后可根據(jù)學(xué)生的掌握情況，逐步引導(dǎo)到采用復(fù)雜結(jié)構(gòu)體及鏈表形式。當(dāng)然它們的數(shù)據(jù)和操作最終都將封裝到類中。

(5) 類的設(shè)計(jì)及對(duì)象的引用

有了抽象數(shù)據(jù)類型和必要的數(shù)據(jù)結(jié)構(gòu)做基礎(chǔ)，下面要考慮的問題就是如何用軟件來實(shí)現(xiàn)，將抽象數(shù)據(jù)類型作為一個(gè)整體自然就引出了封裝的概念，于是就引入了課程的重點(diǎn)內(nèi)容類的設(shè)計(jì)。具有一定數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)是代表實(shí)體屬性的，而操作是實(shí)體所具有的行為，在此可以讓學(xué)生首先用以功能為核心的結(jié)構(gòu)化編程中的“全局函數(shù)”來描述實(shí)體的“行為”，找出其表示自然實(shí)體的不當(dāng)之處。分析將其映射到軟件空間后所引起的在安全性、復(fù)雜性、重用性、易維護(hù)性等方面的問題。通過比較、關(guān)聯(lián)及啟發(fā)的方式，教師可以自然地引出類的設(shè)計(jì)原則與優(yōu)勢(shì)所在，并給出具體的語(yǔ)法規(guī)范。特別是由于“行為”具有了具體的歸屬，自然而然地就涉及到了“全局函數(shù)”與“成員函數(shù)”的區(qū)別，由此非常易于學(xué)生對(duì)封裝后的類中數(shù)據(jù)與方法(或稱為數(shù)據(jù)成員與成員函數(shù))訪問控制要求的理解。

針對(duì)上述的例子，在學(xué)生初次接觸面向?qū)ο蟪绦蛟O(shè)計(jì)的情況下，教師給出類的聲明，假設(shè)采用的是C++語(yǔ)言作為教學(xué)環(huán)境，語(yǔ)法如下：

class Stack //棧類定義

{private:

unsigneddata;

unsigned top;

unsigned size;//堆棧的最大容量

public:

Stack(int n);//構(gòu)建一個(gè)容量為n的棧

~Stack();

bool Push(Type value);//將值value壓棧，成功返回true 否則返回1

bool Pop(Type e); //將當(dāng)前棧頂元素放入e中，成功返回true，否則返回1

void MakeEmpty();//將棧置空

long GetLenth();//得到當(dāng)前棧的元素個(gè)數(shù)

bool IsEmpty();//判斷棧是否為空，空則返回true，否則返回1

bool IsFull();//判斷棧是否滿，滿則返回true否則返回1

}

通過對(duì)該類聲明的理解，啟發(fā)學(xué)生按照一定的語(yǔ)法規(guī)范去具體實(shí)現(xiàn)成員函數(shù)。

下面就是類的應(yīng)用了，此處教學(xué)中的難點(diǎn)是如何區(qū)分類與對(duì)象，通過抽象數(shù)據(jù)類型與具體的實(shí)體來說明“型”與“值”的區(qū)別。最后是算法的計(jì)算機(jī)程序?qū)崿F(xiàn)，在這里教師應(yīng)強(qiáng)調(diào)對(duì)象的“工具”作用，也就是說它是實(shí)現(xiàn)算法的一個(gè)“工具”，能夠提供算法所需要的服務(wù)，而且是一個(gè)封閉的，對(duì)我們來說是透明的服務(wù)。

隨著課程的深入，讓一個(gè)堆棧類繼承于一個(gè)無限制線性表類可以實(shí)現(xiàn)代碼重用及多態(tài)性，通過設(shè)計(jì)堆棧類摸板實(shí)現(xiàn)對(duì)堆棧類的更高的抽象及代碼重用。在應(yīng)用方面，所有用到堆棧的算法都可以用堆棧類產(chǎn)生的對(duì)象為我們提供必要的服務(wù)，如果是類摸板會(huì)提供更方便的應(yīng)用。

4結(jié)束語(yǔ)

正如歷史上第一個(gè)以“大學(xué)的理念”為名著書和演講的人紐曼認(rèn)為的那樣，大學(xué)要培養(yǎng)出具有“哲學(xué)習(xí)性”的人。這種人忠于求真并善于領(lǐng)會(huì)真理的意義，能以全面的眼光觀察事物，能洞悉事物的普遍聯(lián)系，能理解事物各方面的價(jià)值[3]。在大學(xué)，每一門課程都與其它的課程有很大的相關(guān)性，設(shè)置好的教學(xué)組織與授課模式能夠?qū)⒏鱾€(gè)方面知識(shí)融匯貫通，將學(xué)生對(duì)知識(shí)的認(rèn)識(shí)與理解建立在“體系“級(jí)別的層次之上，進(jìn)而更好地用知識(shí)來創(chuàng)造性地解決實(shí)際問題。這也是我們學(xué)習(xí)一門專業(yè)課程最好的效果，也是“研究型”教學(xué)的要求。毫無疑問這種教學(xué)模式也是一種思維方式的培養(yǎng)。

參考文獻(xiàn)：

[1]張洪斌. 計(jì)算機(jī)數(shù)值算法[M]. 北京:中國(guó)礦業(yè)大學(xué)出版社，1996.

[2]陳俊杰. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京:中國(guó)礦業(yè)大學(xué)出版社，1995.

[3]張豈之，謝陽(yáng)舉. 西方近現(xiàn)代大學(xué)理念評(píng)析[J]. 高等教育研究，2003，24(4).

[4]劉智運(yùn). 論高校研究性教學(xué)與研究性學(xué)習(xí)的關(guān)系[J]. 中國(guó)大學(xué)教學(xué)，2006，(2).

[5]謝秉智. 積極推動(dòng)研究性教學(xué)提高大學(xué)生的創(chuàng)新能力[J]. 中國(guó)大學(xué)教學(xué)，2006，(2).