前言：想要寫出一篇令人眼前一亮的文章嗎？我們特意為您整理了5篇計算機程序設(shè)計藝術(shù)范文，相信會為您的寫作帶來幫助，發(fā)現(xiàn)更多的寫作思路和靈感。

計算機程序設(shè)計藝術(shù)范文第1篇

關(guān)鍵詞：算法；程序結(jié)構(gòu)；循環(huán)；遞歸

中圖分類號：TP391文獻(xiàn)標(biāo)識碼：B

文章編號：1672-5913(2007)12-0083-05

1問題的提出

結(jié)構(gòu)化程序設(shè)計中，只有三種基本的結(jié)構(gòu)：順序、選擇和循環(huán)。

順序結(jié)構(gòu)是程序設(shè)計過程中自然形成的，也是三種結(jié)構(gòu)中最簡單的一種。選擇結(jié)構(gòu)與我們?nèi)粘Ｖ惺褂玫淖匀徽Z言“如果...則...否則...”十分相近，只是其嵌套時的二義性在形式上必須有一個明確的規(guī)定。

而循環(huán)結(jié)構(gòu)是三者中最為復(fù)雜的，也是使用最多的。一個算法往往要用循環(huán)結(jié)構(gòu)來描述，一個程序能否正確編寫又往往取決于對循環(huán)結(jié)構(gòu)的正確理解和使用。因此，有必要深入對循環(huán)結(jié)構(gòu)做一個分析。本文從循環(huán)結(jié)構(gòu)的三個要素、循環(huán)結(jié)構(gòu)與程序的閱讀、循環(huán)與遞歸的聯(lián)系等三個方面進(jìn)行分析與論述，而這些在目前的教學(xué)中往往很少提到，甚至是被忽略的。

2循環(huán)結(jié)構(gòu)的三要素

初學(xué)程序設(shè)計的人，對于如何在程序中使用循環(huán)結(jié)構(gòu)實現(xiàn)算法，總覺得不知從何入手，有時即使編出程序，也不盡人意。下面我們從一個簡單的典型實例說起。為了說明問題，本文對有關(guān)編程的問題都以C語言函數(shù)的方式列出解答。

2.1一個典型實例及其兩種解答

例2.1雞兔同籠，有h個頭，f只腳，求雞兔各多少。這是我國古代一個典型的算術(shù)問題?，F(xiàn)在要設(shè)計一個函數(shù)，求出兔子的數(shù)目(求出兔子的數(shù)目，自然就可以得到雞的數(shù)目)。不妨設(shè)這個函數(shù)為：

int hab(int h, int f);

函數(shù)的定義如下：

int rabbit (int h, int f)// h為頭數(shù), f為腳數(shù)

{

int i;

i=h;

while (i＞=0 )

{

if (i*4+(h-i)*2==f) break;

i--;

}

return i; //-1表示該該問題無解。

}

這個程序的運行結(jié)果是正確的，但是很遺憾，這并不是一個完美的程序，盡管很多教科書也是這樣寫的。我們再來看看下面的另一種解法：

int rabbit (int h, int f)// h為頭數(shù), f為腳數(shù)

{

int i;

i=h

while((i＞=0)&& (i*4+(h-i)*2!=f ))

i--;

return i;//-1表示該問題無解。

}

以上兩個程序都用到循環(huán)結(jié)構(gòu)，第一個程序在循環(huán)結(jié)構(gòu)中嵌套了一個選擇結(jié)構(gòu)，并且使用了break語句。而在第二個程序中，無需這樣做。無論從程序的結(jié)構(gòu)，還是從程序的可讀性來說，后者顯得比前者要好得多。那么問題出在哪里呢？

2.2深入分析

比較兩個程序可以發(fā)現(xiàn)，關(guān)鍵是對條件表達(dá)式(i*4+(h-i)*2!=l)的運用。前者把條件表達(dá)式放在循環(huán)體中，后者把它作為循環(huán)條件?？磥恚斜匾獙ρh(huán)結(jié)構(gòu)做深入的分析。

不管一個循環(huán)結(jié)構(gòu)有多復(fù)雜，都可以從以下三個方面來分析：

1) 初始狀態(tài)：所有參與循環(huán)的變量在循環(huán)之前都必須有一個確定的值。

2) 循環(huán)條件：當(dāng)條件滿足時，循環(huán)繼續(xù)，否則循環(huán)終止。循環(huán)條件應(yīng)是一個邏輯表達(dá)式。

3) 循環(huán)體：每次循環(huán)要執(zhí)行的語句。

這就是我們所講的循環(huán)結(jié)構(gòu)三要素。從這個角度再來分析上面的例子，就很容易找到問題的結(jié)癥：(i*4+(h-i)*2!=l)是循環(huán)條件之一，因此不應(yīng)放在循環(huán)體內(nèi)使用。第一種方法雖然也能得到正確的結(jié)果，但并不是好的方法，甚至是不正確的方法。

2.3一個應(yīng)用實例

例2.2 裴波那契序列數(shù)的遞歸表示如下：

f0=0

f1=1

fn=fn-2+fn-1(n＞=2)

對于任意給定的正整數(shù)x，判別其是否在裴波那契序列中。

現(xiàn)在要求判別一個給定的正整數(shù)x是否在裴波那契序列中，一個直觀的判別方法是從f0和f1出發(fā)，不停地求后面的裴波那契序列數(shù)。每得到一個裴波那契序列數(shù)，就同這個待判別數(shù)進(jìn)行比較，直到相等時輸出“真”?；虍?dāng)?shù)玫揭粋€裴波那契序列數(shù)大于這個待判別數(shù)時，輸出“假”。

要實現(xiàn)這個算法，需用到循環(huán)結(jié)構(gòu)。我們來分析一下這個循環(huán)結(jié)構(gòu)的三個要素：

(1) 初始狀態(tài)：f0=0; f1=1，x=?；

(2) 循環(huán)條件：當(dāng)前求得的裴波那契序列數(shù) < 待判別數(shù)x；

(3) 循環(huán)體：計算一個新的裴波那契序列數(shù)。

根據(jù)以上的分析，判別一個給定的正整數(shù)x是否在求裴波那契序列中的C函數(shù)如下：

int in_fib(int x)

{

int f0=0, f1=1;

while (f1＜x)

{

t=f1+f0;

f0=f1;

f1=t;

}

return (x==f1|| x==f0);

}

3循環(huán)結(jié)構(gòu)與程序的閱讀

3.1閱讀的意義

對于計算機程序的閱讀，著名的計算機科學(xué)家克努特曾說過：閱讀他人的計算機程序獲得技巧是極其重要的，但在許許多多的計算機課程中這樣一種訓(xùn)練卻可悲地被忽視了，因此導(dǎo)致計算機極其低效率的使用。

學(xué)習(xí)一種計算機程序設(shè)計語言，不管是匯編語言還是高級語言，一個重要而又常用的方法就是閱讀：閱讀書中的例題，閱讀別人寫的程序，更多的是閱讀自已寫的程序。在某種意義上來說，一個程序是“被閱讀”的。首先是被計算機閱讀，這是毫無疑義的，但更多時候是被人閱讀。

3.2閱讀的方法

閱讀的目的是為了分析程序中的語句是如何實現(xiàn)算法的。對于一些較為復(fù)雜的程序，如果一開始就去分析每一個語句的功能，就很容易掉進(jìn)“迷宮”。因此在分析一個程序時應(yīng)該先分析程序的結(jié)構(gòu)，然后再對每個結(jié)構(gòu)中的語句逐一進(jìn)行跟蹤閱讀。

1. 程序結(jié)構(gòu)的分析

程序結(jié)構(gòu)的分析過程分為兩個步驟：第一是找出組成程序的各種結(jié)構(gòu)，第二是找出這些結(jié)構(gòu)之間的連接方式。

程序結(jié)構(gòu)的分析應(yīng)符合結(jié)構(gòu)化程序設(shè)計的原則。一種結(jié)構(gòu)化程序設(shè)計語言(如C語言，Pascal)，只包含三種基本結(jié)構(gòu)：順序、選擇和循環(huán)。每種結(jié)構(gòu)只有一個入口和一個出口。而各個結(jié)構(gòu)之間的連接方式有兩種：積木式和嵌套式。積木式的連接是一個結(jié)構(gòu)的出口與另一個結(jié)構(gòu)的入口的連接，而嵌套式的連接是在一個結(jié)構(gòu)的內(nèi)部嵌套另一個結(jié)構(gòu)。一般來說，我們應(yīng)先分析出程序中積木式連接的各個結(jié)構(gòu)，然后再找出這些結(jié)構(gòu)中的嵌套式連接的結(jié)構(gòu)。分析程序結(jié)構(gòu)時可以借用一些工具，如N-S圖、偽代碼等，即根據(jù)源程序畫出能反映程序結(jié)構(gòu)的N-S圖或?qū)懗龅刃У膫未a。這是一個與編程過程剛好相反的過程。

2. 語句的跟蹤閱讀

對于順序結(jié)構(gòu)的語句，閱讀是不成問題的。而對于選擇結(jié)構(gòu)的語句，由于與我們平時所用的自然語言比較一致，也不是太大的困難。關(guān)鍵在于，當(dāng)有兩個選擇結(jié)構(gòu)連接時，采用積木式的連接與采用嵌套式連接的差別是很大，有時甚至使得程序運行的結(jié)果截然相反。

循環(huán)結(jié)構(gòu)是三種結(jié)構(gòu)中最為復(fù)雜的一種，對這種結(jié)構(gòu)的跟蹤閱讀可以用列表的方法，將循環(huán)過程中各語句執(zhí)行的結(jié)果一一列出。這個表包含了循環(huán)結(jié)構(gòu)的三個要素。

我們還是從著名的歐幾里德算法說起。

例3.1求兩個正整數(shù)的最大公約數(shù)。

【歐幾里德算法】

E1.[求余數(shù)] 以n除m并令r為所得余數(shù)(0＜=r＜n)。

E2.[余數(shù)為0?] 若r=0, 算法結(jié)束, n即為答案。

E3.[互換] 置mn, nr, 并返回步驟E1。

為了使計算過程更為緊湊，也考慮到當(dāng)n=0時，算法仍然有效，可將以上算法稍作改動如下：

E'1.[n為0?] 若n=0, 算法結(jié)束, m即為答案。

E'2.[求余數(shù)] 以n除m并令r為所得余數(shù)(0＜=n＜n)。

E'3.[互換] 置mn, nr, 并返回步驟E'1。

根據(jù)以上所描述的算法，我們可以用C語言寫出相應(yīng)的函數(shù)：

int gcd(int m,int n)

{

int r;

while (n!=0)

{

r=m%n;

m=n;

n=r;

}

return m;

}

我們通過一組真實的數(shù)據(jù)(例如：m=20, n=12)分析循環(huán)結(jié)構(gòu)的執(zhí)行過程，即對循環(huán)體內(nèi)的語句逐一進(jìn)行跟蹤閱讀，直至循環(huán)條件不成立。分析程序執(zhí)行的過程如下：

閱讀的過程是艱苦的，初學(xué)者對此可能不十分習(xí)慣。但是這是學(xué)習(xí)一種計算機程序設(shè)計語言所必須掌握的方法，也是必須經(jīng)歷的過程。企圖繞開這個過程，尋找別的捷徑是不可能的。

4循環(huán)與遞歸

遞歸是計算科學(xué)中一個很重要的核心概念，它出現(xiàn)在計算科學(xué)的各門分支學(xué)科中，如計算理論基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計方法、程序設(shè)計語言等等。那么，遞歸與循環(huán)有什么聯(lián)系和區(qū)別呢？

在關(guān)于循環(huán)結(jié)構(gòu)三要素中，我們說循環(huán)結(jié)構(gòu)中的第一個要素是循環(huán)的初始狀態(tài)，那么每循環(huán)一次，參與循環(huán)的變量中至少有一個會發(fā)生變化(否則就會出現(xiàn)“死循環(huán)”)。因此，循環(huán)的過程就是從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)，在經(jīng)歷了若干個狀態(tài)之后，到達(dá)終結(jié)狀態(tài)，循環(huán)就結(jié)束。因此可以把一個循環(huán)結(jié)構(gòu)看成是一個有窮狀態(tài)機。在計算理論上，有窮狀態(tài)機能計算的問題，圖靈機必能計算，而圖靈機與遞歸函數(shù)是等價的。從這個意義上講，一個可以用循環(huán)結(jié)構(gòu)解決的問題必然也可以用遞歸方法來解決。對現(xiàn)在一般在大學(xué)一、二年級學(xué)習(xí)程序設(shè)計的學(xué)生來說，還不可能深入討論這個問題。但我們可以用一些典型的實例，通過循環(huán)與遞歸的對比，使得低年級的學(xué)生們對遞歸有一個初步的認(rèn)識。

4.1遞歸的意義與遞歸函數(shù)

我們來看一個簡單的例子。

例4.1求一個正整數(shù)n的階乘。

根據(jù)正整數(shù)階乘的定義n！＝1×2×3×......×n，用一個循環(huán)結(jié)構(gòu)即可很容易編寫出計算階乘的程序。如果用一個函數(shù)f(n)來表示n的階乘，也可以這樣來定義f(n)：

1 n=0

f(n)={

n?f(n-1)n＞0

在定義f(n)時又用到f這個函數(shù)，這就是遞歸。注意，在定義式中用到函數(shù)f，但它的自變量是n-1，計算n-1的階乘要比計算n的階乘容易一些。而且當(dāng)n=0時，可以直接得到答案f(0)=1。

例4.2求兩個正整數(shù)的最小公倍數(shù)。

歐幾里德算法(見例3.1)與以下的遞歸函數(shù)是等價的：

m n=0

gcd(m,n)= {

gcd(n,m%n)n＞0

在這里，當(dāng)n>0時，計算的是n和m%n的最小公倍數(shù)。顯然，這時的兩個正整數(shù)要比原來的兩個正整數(shù)(m, n)要小，計算也變得容易一些。

通過以上的例子，我們可以這樣來理解遞歸的意義：把一個復(fù)雜的、規(guī)模較大的問題轉(zhuǎn)化為簡單的、規(guī)模較小的同一個問題，直至可以直接得到問題的解。

4.2用遞歸函數(shù)取代循環(huán)結(jié)構(gòu)

一個程序如果可以用循環(huán)結(jié)構(gòu)來實現(xiàn)，那么也可以用一個遞歸函數(shù)來實現(xiàn)。我們先來看一個簡單的例子。

例4.3求一個有n個元素的數(shù)組中的最大元素。

用循環(huán)結(jié)構(gòu)的方法如下：

int max(int a[])

{

int i, m;

m=a[0]

for (i=1; i＜10,i++)

if(max＜a[i])m=a[i];

return m;

}

用遞歸函數(shù)。設(shè)一遞歸函數(shù)max(a,k)是求a數(shù)組中第k個元素及其后所有元素的最大者：

a[k]k=n-1;

max(a,k)= {

a[k]＞max(a,k+1)?a[k]：max(a,k+1) k＜n-1

用C語言編寫的函數(shù)如下：

int max(int a[], int k, int n)

{ int m;

if (k==n-1)return ( a[k] )

else {m=max(a,k+1);

return ( a[k]＞m?a[k]：m ); }

}

這是一個簡單的例子，下面再看一個較為復(fù)雜性的例子。

例4.4用遞歸函數(shù)求解例2.1。

用遞歸函數(shù)來求解例2.1，應(yīng)如何考慮呢？正如以上所說，遞歸的意義是把一個復(fù)雜的、規(guī)模較大的問題轉(zhuǎn)化為簡單的、規(guī)模較小的同一個問題，直至可以直接得到問題的解。因此我們可以這樣來考慮：把籠中的一只雞抓走，籠中的兔子的數(shù)目是不變的，顯然這仍然是雞兔同籠的問題，但少了一只雞，問題就變得簡單了一點。當(dāng)所有的雞都被抓走時，剩下的都是兔，這時就可以直接得到答案――腿數(shù)除以頭數(shù)就是兔子的數(shù)目。

我們用robb(h,g)這樣一個函數(shù)表示求兔子的數(shù)目，參數(shù)h、g分別表示頭數(shù)和腿數(shù)，因此有：

robb(x,y)=robb(x-1,y-2)

但在什么情況下能直接得到結(jié)果呢？顯然，當(dāng)雞全部抓走只留下兔子時，就可以直接得到答案，這時腿數(shù)應(yīng)是頭的4倍：

roob(x,y)=x當(dāng)4*x=y

另外還要考慮在什么情況下問題沒有解。顯然，當(dāng)4*h＜g時，這個問題無解。

x

4*x=y

robb(x,y)={ robb(x-1,y-2)　4*x＞y

-1

4*x＜y(-1表示問題無解)

在求得兔子的數(shù)目之后，只要用總數(shù)減去兔子的數(shù)目，就能求出雞的數(shù)目。

結(jié)束語

程序設(shè)計作為一門學(xué)科，經(jīng)歷了子程序、高級語言、結(jié)構(gòu)化程序設(shè)計三個里程碑[2]。近十幾年興起的面向?qū)ο蟪绦蛟O(shè)計可以說是第四個里程碑。程序設(shè)計在計算科學(xué)這門年輕的學(xué)科中，是一門“古老”的分支學(xué)科，又是一門久經(jīng)不衰的學(xué)科。計算科學(xué)中的許多新思想、新方法、新技術(shù)都首先體現(xiàn)在程序設(shè)計上。這種現(xiàn)象使我們不得不領(lǐng)悟到，這門課程中的許多知識反映了計算科學(xué)深刻的內(nèi)涵，程序設(shè)計的教學(xué)應(yīng)體現(xiàn)這一點。例如上述的循環(huán)結(jié)構(gòu)，就很值得我們?nèi)ヌ接憽１疚奶岢龅囊恍┯^點，確實很膚淺，希望能起到一個拋磚引玉的作用。

參考文獻(xiàn)：

[1] 蘇運霖譯. 計算機程序設(shè)計藝術(shù) 第1卷 基本算法［M］. 北京：國防工業(yè)出版社，2002.

[2] 王選. 王選文集［M］.北京大學(xué)出版社，1997.

[3] 趙致琢. 計算科學(xué)導(dǎo)論(第二版)［M］. 北京：科學(xué)出版社，1998.

收稿日期：2006-5-27

通信地址：廣東省廣州市 華南師范大學(xué)計算機學(xué)院， 510631

計算機程序設(shè)計藝術(shù)范文第2篇

關(guān)鍵詞:算法;復(fù)雜認(rèn)知技能;4C/ID

尼克勞斯•威茨,結(jié)構(gòu)化程序設(shè)計的首創(chuàng)者和圖靈獎獲得者,提出了一個著名論斷:程序=算法+數(shù)據(jù)結(jié)構(gòu)。這說明了算法的重要地位。什么是算法?算法和程序設(shè)計技術(shù)的先驅(qū)者高德納把算法比喻成菜譜。他認(rèn)為“算法是一組有窮的規(guī)則,這些規(guī)則給出求解特定類型問題的運算序列”,他強調(diào)“我們不僅要算法,而且還要在某種不明確定義的意義下的好算法”[1]――算法分析?！陡叩葘W(xué)校計算機科學(xué)與技術(shù)專業(yè)實踐教學(xué)體系與規(guī)范》把算法設(shè)計與分析能力界定為計算機專業(yè)高級人才的基本學(xué)科能力之一[2]?？梢?“算法設(shè)計與分析”課程的重要性。然而,學(xué)生普遍覺得該課程難學(xué)。為了解決這個問題,應(yīng)用四要素教學(xué)設(shè)計模型(以下簡稱4C/ID)進(jìn)行教學(xué)改革。4C/ID是提高復(fù)雜認(rèn)知技能的方法,在國外,4C/ID的研究已有30年的歷史,曾經(jīng)成功地將4C/ID應(yīng)用與計算機編程。在國內(nèi),4C/ID的研究還處于起步階段。本文主要研究了4C/ID在“算法設(shè)計與分析”課程教學(xué)中的實踐。

1課程教學(xué)中存在的問題

1.1學(xué)生學(xué)習(xí)有畏難情緒

算法是問題的程序化解決方案[3]。首先,要理解問題,確定問題的條件和應(yīng)用范圍。然后,建立數(shù)學(xué)模型。最后,證明算法的正確性和分析算法的效率。這需要微積分、線性代數(shù)、離散數(shù)學(xué)等數(shù)學(xué)知識。所以,對于這門復(fù)雜、抽象的課程,學(xué)生自然感到難學(xué)。

1.2算法實現(xiàn)有難度

算法實現(xiàn)指編制與調(diào)試算法。算法實現(xiàn)有助于加深對算法的理解,是不可缺少的環(huán)節(jié)。算法的實現(xiàn)取決于:(1)豐富的程序設(shè)計語言和數(shù)據(jù)結(jié)構(gòu)實踐經(jīng)驗。如學(xué)生在程序調(diào)試時經(jīng)常出的錯是缺少函數(shù)聲明;在進(jìn)行“分支限界”實訓(xùn)時,很多學(xué)生由于沒有掌握隊列而無法實現(xiàn)裝載問題算法。這是程序設(shè)計語言和數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)不扎實造成的。過多的出錯會嚴(yán)重影響上機實踐的質(zhì)量,造成學(xué)生不愿動手。(2)對算法的理解。算法通常是由偽代碼來描述的,如果不理解算法,很難準(zhǔn)確地將算法轉(zhuǎn)換成可以運行的程序。如果這兩個問題不能很好地解決,算法設(shè)計與分析能力的培養(yǎng)就成為一句空話。

2 “4C/ID”是解決問題的途徑

算法設(shè)計與分析是復(fù)雜的認(rèn)知技能,其構(gòu)成見圖1。復(fù)雜的認(rèn)知技能是由一系列的技能所構(gòu)成,其中一部分構(gòu)成技能體現(xiàn)為自動的處理過程,其它多數(shù)的構(gòu)成技能涉及認(rèn)知的領(lǐng)域[4]。從圖1可以看出,這是一個復(fù)雜的學(xué)習(xí)過程。如果從頭到尾地講解給學(xué)生聽,然后再讓學(xué)生上機實踐,這就不能了解學(xué)生哪些技能掌握了,哪些沒有掌握,從而影響了上機實踐的質(zhì)量。而且,直線式講解不符合問題求解的規(guī)律,有些過程需要反復(fù)實踐,有些過程需要思考和補充相關(guān)信息。4C/ID是面向復(fù)雜認(rèn)知技能培訓(xùn)的教學(xué)設(shè)計模型,由約倫•范麥里恩伯爾基于學(xué)習(xí)和信息加工的認(rèn)知心理學(xué)理論創(chuàng)造。該模型之所以能提高復(fù)雜認(rèn)知技能的原因是它將復(fù)雜認(rèn)知技能分成再用性構(gòu)成技能和非再用性構(gòu)成技能,并對它們分別進(jìn)行實際練習(xí)設(shè)計和信息呈現(xiàn)設(shè)計。再用性構(gòu)成技能是指在不同問題情境中以極為類似的方式而操作的技能,非再用性構(gòu)成技能是指在不同的問題情境中進(jìn)行不同操作的技能[5]。再用性構(gòu)成技能的熟練掌握可以解決問題中熟悉的方面,非再用性構(gòu)成技能通過圖式建構(gòu)可以運用于問題情境中新的、不熟悉的方面。兩者相互促進(jìn),能提高解決問題的整體水平。所以,將4C/ID應(yīng)用于“算法設(shè)計與分析”教學(xué)中會比傳統(tǒng)的教學(xué)方法更能提高算法設(shè)計與分析的能力。

3 “4C/ID”的教學(xué)實踐

4C/ID分成教學(xué)分析和教學(xué)設(shè)計兩個部分。這兩個部分又各分成兩層,共4層。它們是:(1)原理性技能的分解;(2)構(gòu)成技能及相關(guān)知識的分析;(3)教學(xué)方法的選擇;(4)訓(xùn)練策略的合成。

3.1原理性技能的分解

4C/ID的第一步是將復(fù)雜認(rèn)知技能分成不同類型的構(gòu)成技能。分解的過程依據(jù)一定的原則,因此稱為“原理性”分解。原理性技能的分解遵循以下的原則:(1)識別。識別組成復(fù)雜認(rèn)知技能的構(gòu)成技能,產(chǎn)生一個技能分層結(jié)構(gòu)。這個分層結(jié)構(gòu)包含了確定的構(gòu)成技能及它們之間的關(guān)系。(2)描述。清晰描述每個構(gòu)成技能。(3)分類。將構(gòu)成技能分成用于培訓(xùn)和不用于培訓(xùn)的技能。對于用于培訓(xùn)的構(gòu)成技能將進(jìn)一步分成再用性構(gòu)成技能和非再用性構(gòu)成技能。(4)排序。將被選擇用于培訓(xùn)的構(gòu)成技能排序。這里重點講一下如何區(qū)別再用性構(gòu)成技能和非再用性構(gòu)成技能。它們的區(qū)別主要反映在執(zhí)行時表現(xiàn)不同。再用性構(gòu)成技能的表現(xiàn)特征為:(1)執(zhí)行很快;(2)顯示錯誤很少或沒有;(3)能和其他構(gòu)成技能同時執(zhí)行;(4)只能在特定的問題情境中產(chǎn)生上述特點,不易遷移到新的、不熟悉的情境中。再用性構(gòu)成技能的執(zhí)行過程可以被制定成一套執(zhí)行程序,只要配以必備的知識,總能成功的執(zhí)行。非再用性構(gòu)成技能的表現(xiàn)特點:(1)執(zhí)行緩慢;(2)執(zhí)行過程容易出錯;(3)不適合與其他的非再用性構(gòu)成技能同時執(zhí)行。如,深度優(yōu)先搜索算法就是再用性構(gòu)成技能,在求解動態(tài)規(guī)劃問題時分析最優(yōu)子結(jié)構(gòu)是非再用性構(gòu)成技能。

3.2構(gòu)成技能及相關(guān)知識的分析

構(gòu)成技能的分析方法有程序分析法和基于規(guī)則的分析法。程序分析法用于可以觀察的、具有先后執(zhí)行順序的再用性構(gòu)成技能,基于規(guī)則的分析法用于不可觀察的、不具有明顯先后執(zhí)行順序的非再用性構(gòu)成技能。

3.2.1再用性構(gòu)成技能

深度優(yōu)先搜索可以表示成固定的“算法”,如圖2。再用性構(gòu)成技能的成功執(zhí)行往往需要必備知識。必備知識包括事實、概念、原則等,見圖2中的注釋。

3.2.2非再用性構(gòu)成技能

非再用性構(gòu)成技能的執(zhí)行過程不能表示成固定的“程序”,它的執(zhí)行依賴于支撐性知識和策略性知識。其實,非再用性構(gòu)成技能的分析就是對支撐性知識和策略性知識的分析。支撐性知識的分析涉及到復(fù)雜的認(rèn)知圖式。復(fù)雜的認(rèn)知圖式由不同的、有相互關(guān)系的認(rèn)知單元所組成,這些認(rèn)知單元可以是陳述、概念、原理等。支撐性知識的分析是建立在對關(guān)系分析的基礎(chǔ)上,再從相關(guān)的關(guān)系中找出所有有用的認(rèn)知單元。主要的關(guān)系包括種類關(guān)系、部分關(guān)系、方位關(guān)系、原因―結(jié)果關(guān)系、相似關(guān)系。確定關(guān)系和認(rèn)知單元后,用概念模型、目標(biāo)―方案層次結(jié)構(gòu)、原理功能模型、心智模型組織和顯示認(rèn)知單元及它們之間的關(guān)系。策略性知識的分析主要采用解決問題的系統(tǒng)方法。該方法的目的是要建立一個描述解決問題的模型。為了建立這個模型,讓專家和教師解決他們領(lǐng)域內(nèi)和該問題相似的經(jīng)典問題,并且要求他們在思考問題的同時把思路講出來,這些話便被整理成描述解決問題的模型。如,在求解動態(tài)規(guī)劃問題時可以選擇矩陣鏈相乘、求最長公共子序列、最優(yōu)二叉搜索樹、裝配線調(diào)度等例子,通過分析經(jīng)典教材來建立描述解決問題的模型。

3.3教學(xué)方法選擇和訓(xùn)練策略合成

教學(xué)方法通過現(xiàn)則支持再用性、非再用性構(gòu)成技能獲得的實際練習(xí)設(shè)計和信息呈現(xiàn)設(shè)計。學(xué)習(xí)者通過反復(fù)訓(xùn)練都能掌握再用性構(gòu)成技能,相應(yīng)的信息呈現(xiàn)可以采用分割、示范和搭建腳手架的方法。分割的作用是避免認(rèn)知負(fù)荷,在同一時間內(nèi)僅提供直接的、可利用的信息。專家示范可以形象地說明規(guī)則和程序的運作。搭建腳手架就像幫助系統(tǒng)一樣,能因人而異地

提供及時的、直接有效的信息。非再用性構(gòu)成技能的獲得取決于圖式建構(gòu)。圖式建構(gòu)是指把低水平的圖式整合到高水平圖式中,逐漸形成更加復(fù)雜的圖式。復(fù)雜的圖式有助于非再用性構(gòu)成技能的獲得。圖式建構(gòu)取決于歸納的程度。歸納的作用為:(1)創(chuàng)建新的圖式;(2)調(diào)整已有圖式,使之適合更廣泛的事件。相應(yīng)的信息呈現(xiàn)方式必須能為歸納所用。因此,必須要對知識精制化。精制化是指將新的知識整合到記憶中已有的認(rèn)知結(jié)構(gòu)。這個過程通過類比來實現(xiàn)。

復(fù)雜認(rèn)知技能的獲得是建立在整體任務(wù)實踐的基礎(chǔ)上。因此,訓(xùn)練策略的合成是形成復(fù)雜認(rèn)知技能的關(guān)鍵。這個過程必須遵循以下原則:(1)在實踐開始階段,為再用性和非再用性構(gòu)成技能提供需要的必備知識和支撐知識;(2)隨著專長的提高,相應(yīng)地減少知識的呈現(xiàn),直至學(xué)習(xí)者能夠獨立地、在不需要幫助的情況下面對真實的問題。這時,學(xué)習(xí)者獲得了復(fù)雜認(rèn)知技能。

4結(jié)論

經(jīng)過實踐檢驗,4C/ID能有效提高復(fù)雜認(rèn)知技能。應(yīng)用4C/ID于“算法設(shè)計與分析”課程,效果體現(xiàn)在兩方面:(1)解決問題的能力提高了。以前,答題是把算法從頭到尾背過來的,算法常有缺漏或搞亂算法語句順序?，F(xiàn)在,答題內(nèi)容以實踐的經(jīng)驗體會居多,答對率提高了16%。(2)考證通過率提高了?！八惴ㄔO(shè)計與分析”是一門綜合性的課程,算法設(shè)計與分析能力的提高深化了學(xué)生對“程序設(shè)計語言”、“數(shù)據(jù)結(jié)構(gòu)”等課程的學(xué)習(xí),考證通過率也增加了。4C/ID不盡人意之處在于要費很多時間去分析。所以,4C/ID一般和教學(xué)設(shè)計系統(tǒng)一起使用。

參考文獻(xiàn):

[1] DONALD E.KNUTH. 計算機程序設(shè)計藝術(shù):基本算法[M]. 蘇運霖,譯.北京:國防工業(yè)出版社,2007.

[2] 教育部高等學(xué)校計算機科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會. 高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)實踐教學(xué)體系與規(guī)范[M]. 北京:清華大學(xué)出版社,2008.

[3] Anany Levitin. 算法設(shè)計與分析基礎(chǔ)[M]. 潘彥,譯. 北京:清華大學(xué)出版社,2007.

[4] Jeroen J.G.Van Merrienboer,Paul A. Kirschner.Ten Steps to Complex Learning:A Systematic Approach to Four-component Instructional Design[M]. New Jersey:LAWRENCE ERLBAUM ASSOCIATES,2007.

[5] 羅伯特D.坦尼森,弗蘭茲•肖特,諾伯特M.西爾,等. 教學(xué)設(shè)計的國際觀:理論•研究•模型[M]. 任友群,裴新寧,譯. 北京:教育科學(xué)出版社,2007.

Improve Complex Cognitive Skills on "Algorithms Design and Analysis" Course

LUO Yi-sheng

(Department of Technology Education, Guangdong Polytechnic Normal University, Guangzhou 510630,China)

計算機程序設(shè)計藝術(shù)范文第3篇

數(shù)學(xué)在人類文明的發(fā)展歷史中發(fā)揮著重要的作用，推動了重大的科學(xué)技術(shù)進(jìn)步。尤其是到了二十世紀(jì)中葉以后，數(shù)學(xué)的理論研究與實際應(yīng)用之間的時間差已大大縮短。當(dāng)前，隨著計算機應(yīng)用的普及，信息的數(shù)字化和信息通道的大規(guī)模聯(lián)網(wǎng)，依據(jù)數(shù)學(xué)所作的創(chuàng)造設(shè)想已經(jīng)達(dá)到可即時試驗、即時實施的地步。數(shù)學(xué)技術(shù)一直是一種應(yīng)用最廣泛、最直接、最及時、最富創(chuàng)造力的實用技術(shù)。數(shù)學(xué)為計算機的發(fā)明和發(fā)展壯大提供了堅實的理論基礎(chǔ)。早在1936年，英國數(shù)學(xué)家圖靈(Turing)發(fā)表了對計算機具有奠基意義的論文《論可計算數(shù)及其在判定問題上的應(yīng)用》，里面提出了計算的圖靈機模型，該模型即為現(xiàn)代計算機模型的原型。為紀(jì)念數(shù)學(xué)家圖靈，美國計算機學(xué)會于1966年設(shè)立了計算機界最負(fù)盛名的“圖靈”獎，以表彰那些對計算機事業(yè)做出重要貢獻(xiàn)的個人。數(shù)學(xué)是所有工科的基礎(chǔ)，其中離散數(shù)學(xué)已經(jīng)成為計算機科學(xué)發(fā)展的理論基礎(chǔ)。圖靈獎的獲得者中有不少是學(xué)數(shù)學(xué)或者數(shù)學(xué)家出身。1974年獲獎的DonaldE.Knuth被稱為現(xiàn)代計算機之父，之前在加州理工獲得數(shù)學(xué)博士學(xué)位，著有經(jīng)典著作《計算機程序設(shè)計藝術(shù)》4卷。RichardM.Karp于1985年獲獎，之前在哈佛大學(xué)獲應(yīng)用數(shù)學(xué)博士學(xué)位。1986獲獎的RobertE.Tarjan在斯坦福大學(xué)同時獲得數(shù)學(xué)和計算機的博士學(xué)位，主要研究圖論、算法和數(shù)據(jù)結(jié)構(gòu)。當(dāng)前計算機理論及應(yīng)用的壯大和發(fā)展更是離不開近代數(shù)學(xué)的發(fā)展，將計算機與數(shù)學(xué)的發(fā)展分割開來既不合理也不現(xiàn)實，和所有學(xué)科一樣，計算機領(lǐng)域也有自己的問題，比如什么是可計算的，什么是實際可計算的，這些計算模型本質(zhì)上是數(shù)學(xué)的應(yīng)用。離散結(jié)構(gòu)上的算法研究無疑是計算機科學(xué)中的重要領(lǐng)域，研究算法需有扎實的數(shù)學(xué)功底，就機器學(xué)習(xí)領(lǐng)域的研究而言，通常要對所處理的數(shù)據(jù)建立不同的數(shù)學(xué)模型如分類模型、回歸模型和排序模型。一般地，先針對這些問題建立特定的模型，然后采用有效的優(yōu)化算法來求解這些模型。應(yīng)用數(shù)學(xué)如矩陣論、多元統(tǒng)計分析和最優(yōu)化理論可以為深入地研究機器學(xué)習(xí)領(lǐng)域提供理論基礎(chǔ)。在實際的工作中，會經(jīng)?？吹綌?shù)學(xué)基礎(chǔ)好、具有一定數(shù)學(xué)素養(yǎng)的人解決問題會游刃有余且后勁足，學(xué)習(xí)新事物和新東西會比較快，會表現(xiàn)出一定的創(chuàng)造性。但是當(dāng)前大學(xué)的課程安排普遍存在對學(xué)生的數(shù)學(xué)學(xué)習(xí)的掌握程度不是很重視，導(dǎo)致學(xué)生對數(shù)學(xué)課的態(tài)度停留在學(xué)習(xí)時僅了解，一學(xué)完就全忘，到用時就迷惑的一知半解狀態(tài)。教師在教授專業(yè)課和專業(yè)基礎(chǔ)課的過程中，沒有引導(dǎo)學(xué)生深入地發(fā)掘理論背后的數(shù)學(xué)本質(zhì)，導(dǎo)致學(xué)生對計算機科學(xué)理論的理解只能停留在表面，憑機械性記憶而沒有徹底理解。鑒于上述數(shù)學(xué)在計算機的發(fā)明發(fā)展和實際工作中的重要作用，因此，在計算機教育的過程中，迫切地需要培養(yǎng)學(xué)生的數(shù)學(xué)素養(yǎng)以滿足現(xiàn)實工作和學(xué)習(xí)中解決實際問題的需要。

二、數(shù)學(xué)素養(yǎng)的培養(yǎng)

《算法設(shè)計與分析》是計算機專業(yè)的一門重要的專業(yè)課，有利于培養(yǎng)學(xué)生分析問題和解決問題的能力，為學(xué)生學(xué)習(xí)后續(xù)課程打下堅實的基礎(chǔ)。下面結(jié)合這門課程來談?wù)勗谟嬎銠C課程中如何提高學(xué)生的數(shù)學(xué)素養(yǎng)。

(一)結(jié)合算法的發(fā)明史來講解算法

深入學(xué)習(xí)計算機科學(xué)需要有良好的數(shù)學(xué)基礎(chǔ)，對于算法的學(xué)習(xí)更是如此。研究算法的圖靈獎獲得者中有很多是數(shù)學(xué)家或者學(xué)數(shù)學(xué)出身，如圖論中有很多算法是以前面提到的RobertE.Tarjan的名字命名的，著名的Dijkstra最短路徑算法由EdsgerW.Dijkstra發(fā)明，而他2000年退休前一直是美國Taxas大學(xué)的計算機科學(xué)和數(shù)學(xué)教授。前面提到的DonaldE.Knuth則是字符串匹配算法KMP算法的發(fā)明人。給學(xué)生講解算法的發(fā)明歷史一方面幫助學(xué)生了解發(fā)明算法的背景和發(fā)明過程，激發(fā)學(xué)生的創(chuàng)新欲望；另一方面讓學(xué)生認(rèn)識到數(shù)學(xué)的重要性和其在該課程所涉及的領(lǐng)域中發(fā)揮的重要作用。

(二)結(jié)合學(xué)生所掌握的數(shù)學(xué)知識來講解算法

修讀該門課程的對象一般為大學(xué)高年級學(xué)生，他們之前應(yīng)該修過其他的數(shù)學(xué)課程，如高等數(shù)學(xué)(數(shù)學(xué)分析)、線性代數(shù)和離散數(shù)學(xué)。通常教師在講授該課程的過程中會認(rèn)識到離散數(shù)學(xué)在其中發(fā)揮的作用，會有意識地提及離散數(shù)學(xué)的知識，但實際上學(xué)生學(xué)習(xí)的高等數(shù)學(xué)或線性代數(shù)的知識對理解該門課程也是有幫助的。下面通過一個例子來說明數(shù)學(xué)知識對理解算法正確性的重要作用。設(shè)計完算法如何證明算法的正確性呢？對于順序結(jié)構(gòu)和選擇結(jié)構(gòu)比較好驗證，而對于循環(huán)結(jié)構(gòu)就使用循環(huán)不變量(LoopInvariant)來證明。而循環(huán)不變量的證明實際上借鑒了數(shù)學(xué)歸納法的思想：循環(huán)發(fā)生前某個循環(huán)不變量為真，循環(huán)進(jìn)行的過程中保持為真，那么循環(huán)結(jié)束時，該循環(huán)不變量仍然為真。因此可以斷定：無論循環(huán)體循環(huán)多少次，該循環(huán)不變量總為真。其他的例子，包括：比較算法的時間復(fù)雜度時可以引入高等數(shù)學(xué)中的無窮小量來講解；計算時間復(fù)雜度也會涉及到利用無窮級數(shù)的估計等等。

(三)結(jié)合數(shù)學(xué)工具來可視化算法

理論的發(fā)明通常是從簡單直觀的例子中歸納得來的，數(shù)學(xué)工具可以幫助我們理解和可視化算法。

(四)結(jié)合數(shù)學(xué)抽象思維來幫助學(xué)生理解算法

數(shù)學(xué)的抽象思維可以幫助學(xué)生站在更高的角度來看待問題和算法之間的聯(lián)系。算法通常是針對某一類問題的，而如何對問題進(jìn)行歸類，如何選擇合適的算法解決是值得學(xué)生去探究的問題。講解算法時，應(yīng)該幫助學(xué)生抽象出問題的本質(zhì)，同時注意算法之間的聯(lián)系與區(qū)別。計算點對之間的距離是算法設(shè)計中一個經(jīng)典問題，如果源點單一，可采用Dijkstra最短路徑算法，而計算圖中任意點之間的最短路徑，使用Floyd-Warshall最短路徑算法會合適一些，但是如果圖上的權(quán)重存在負(fù)值，那就要用帶松弛操作的Bellman-Ford算法求解。了解了這些知識后，學(xué)生在把問題抽象成特定的算法模型時，就可以正確地使用合適的算法了。其他問題包括使用矩陣胚理論來證明貪心算法的正確性以及靈活應(yīng)用動態(tài)規(guī)劃來求解離散結(jié)構(gòu)上的最優(yōu)化問題等等。